summaryrefslogtreecommitdiff
path: root/HACKING
diff options
context:
space:
mode:
authorEric S. Raymond <esr@thyrsus.com>2006-07-31 16:06:43 +0000
committerEric S. Raymond <esr@thyrsus.com>2006-07-31 16:06:43 +0000
commita20a1f0dd96ab7c227e3f8c16155030670b91844 (patch)
tree543fa9518e36e6f850666424ff371c6a7c894ab4 /HACKING
parent0f2fd319dd19840758662065bae13c643a615195 (diff)
downloadgpsd-a20a1f0dd96ab7c227e3f8c16155030670b91844.tar.gz
HTMLize the HACKING file.
Diffstat (limited to 'HACKING')
-rw-r--r--HACKING1088
1 files changed, 0 insertions, 1088 deletions
diff --git a/HACKING b/HACKING
deleted file mode 100644
index 54795b97..00000000
--- a/HACKING
+++ /dev/null
@@ -1,1088 +0,0 @@
-This is the Hacker's Guide to gpsd. If you're viewing it with Emacs, try
-doing Ctl-C Ctl-t and browsing through the outline headers. Ctl-C Ctl-a
-will unfold them again.
-
-If you're looking for things to hack on, first see the TODO file.
-
-** Goals and philosophy of the project
-
-If the GPSD project ever needs a slogan, it will be "Hide the ugliness!"
-GPS technology works, but is baroque, ugly and poorly documented. Our
-job is to know the grotty details so nobody else has to.
-
-*** Audience and supported hardware
-
-Our paradigm user, the one we have in mind when making design choices,
-is running navigational or wardriving software on a Linux laptop or
-PDA. Some of our developers are actively interested in supporting
-GPS-with-SBC (Single-Board-Computer) hardware such as is used in
-balloon telemetry, marine navigation, and aviation.
-
-These two use cases have similar issues in areas like client
-interfaces and power/duty-cycle management. The one place where
-they differ substantially is that in the SBC case we generally
-know in advance what devices will be connected and when. Thus, by
-designing for the less predictable laptop/PDA environment, we
-cover both. But it is not by accident that the source code can be built
-with support for only any single GPS type compiled in.
-
-While we will support survey-grade GPSes when and if we have that
-hardware for testing, our focus will probably remain on inexpensive
-and readily-available consumer-grade GPS hardware, especially GPS
-mice.
-
-*** The time and location service
-
-The primary aim of the GPSD project is to support a simple
-time-and-location service for users and their geographically-aware
-applications.
-
-A GPS is a device for delivering fourteen numbers: x, y, z, t, vx, vy, vz,
-and error estimates for each of these seven coordinates. The gpsd daemon's
-job is to deliver these numbers to user applications with minimum fuss.
-
-'Minimum fuss' means that the only action the user should have to take
-to enable location service is to plug in a GPS. The gpsd daemon, and its
-associated hotplug scripts or local equivalent, is responsible for
-automatically configuring itself. That includes autobauding,
-handshaking with the device, determining the correct mode or protocol
-to use, and issuing any device-specific initializations required.
-
-Features (such as GPS type or serial-parameter switches) that would
-require the user to perform administrative actions to enable location
-service will be rejected. GPSes that cannot be autoconfigured will
-not be supported. 99% of the GPS hardware on the market in 2005 is
-autoconfigurable, and the design direction of GPS chipsets is such
-that this percentage will rise rather than fall; we deliberately
-choose simplicity of interface and zero administration over 100%
-coverage.
-
-Here is a concrete example of how this principle applies. At least
-one very low-end GPS chipset does not deliver correct checksums on the
-packets it ships to a host unless it has a fix. Typically, GPSes do
-not have a fix when they are plugged in, at the time gpsd must
-recognize and autoconfigure the device. Thus, supporting this chipset
-would require that we either (a) disable packet integrity checking in
-the autoconfiguration code, making detection of other more
-well-behaved devices unreliable, or (b) add an invocation switch to
-disable packet integrity checking for that chipset alone. We refuse
-to do either, and do not support this chipset.
-
-*** The testing and tuning tools
-
-Another principal goal of the GPSD software is that it be able to
-demonstrate its own correctness, give technical users good tools for
-measuring GPS accuracy and diagnosis of GPS idiosyncrasies, and
-provide a test framework for gpsd-using applications.
-
-Accordingly, we support the gpsfake tool that simulates a GPS using
-recorded or synthetic log data. We support gpsprof, which collects
-accuracy and latency statistics on GPSes and the GPS+gpsd combination.
-And we include a comprehensive regression-test suite with the package.
-These tools are not accidents, they are essential to ensure that the
-basic GPS-monitoring code is not merely correct but *demonstrably*
-correct.
-
-We support a tool, sirfmon, which is a low-level packet monitor and
-diagnostic tool for the chipset with 80% market share. sirfmon is
-capable of tuning some device-specific control settings such as the
-SiRF static-navigation mode. A future direction of the project is to
-support diagnostic monitoring and tuning for other chipsets.
-
-*** The upgrading tools
-
-A secondary aim of the GPSD project is to support GPS firmware
-upgrades under open-source operating systems, freeing GPS users from
-reliance on closed-source vendor tools and closed-source operating
-systems.
-
-We have made a first step in that direction with the initial pre-alpha
-version of gpsflash, currently supporting SiRF chips only. A future
-direction of the project is to have gpsflash support firmare upgrades
-for other chipsets.
-
-*** The GPS/GNSS monitoring tools
-
-Another secondary goal of the project is to provide open-source tools
-for diagnostic monitoring and accuracy profiling not just of
-individual GPSes but of the GPS/GNSS network itself. The protocols
-(such as IS-GPS-200 for satellite downlink and RCTM104 for
-differential-GPS corrections) are notoriously poorly documented, and
-open-source tools for interpreting them have in the past been hard
-to find and only sporadically maintained.
-
-We aim to remedy this. Our design goal is to provide lossless
-translators between these protocols and readable, documented
-text-stream formats.
-
-We currently provide a tool for decoding RTCM104 reports on satellite
-health, almanacs, and pseudorange information from differential-GPS
-radios and reference stations. A future direction of the project is
-to support an RTCM104 encoder.
-
-** Contribution guidelines
-
-*** Send patches in diff -u or -c format
-
-We prefer diff -u format, but diff -c is acceptable. Do not send
-patches in the default (-e or ed) mode, as they are too brittle.
-
-Before shipping a patch, you should go through the following checklist:
-
-(1) If you are introducing a new feature or driver, include a
- documentation patch.
-
-(2) Use the regression-test suite -- "make testregress" -- to check
- that your patch doesn't break the handling of any already-supported GPS.
-
-(3) If you have valgrind(1) on your development system, run
- valgrind-audit and look out for reports of memory leaks and
- other dynamic-allocation problems (see <http://valgrind.org> for
- a description of this tool if you don't already know about it).
- If you can't run valgrind. tell us that you couldn't do it.
-
-(4) If you have splint(1) on your development system, make sure the
- patched code displays no warnings when you run 'make
- splint' (see <http://www.splint.org> for further description of
- this tool if you don't already know about it). If you can't run
- splint, tell us that you couldn't do it.
-
-If you are contributing a driver for a new GPS, please also do the
-following things:
-
-(5) Send us a representative sample of the GPS output for future
- regression-testing.
-
-(6) Write a hardware entry describing the GPS for the hardware page at
- <http://gpsd.berlios.de/hardware.html>.
-
-There's a whole section on adding new drivers later in this document.
-
-*** The license on contributions
-
-The GPSD libraries are under the BSD license. Please do not send
-contributions with GPL attached!
-
-The reason for this policy is to avoid making people nervous about
-linking the GPSD libraries to applications that may be under other
-licenses (such as MIT, BSD, AFL, etc.).
-
-*** Don't add invocation options!
-
-If you send a patch that adds a command-line option to the daemon, it
-will almost certainly be refused. Ditto for any patch that requires
-gpsd to parse a dotfile.
-
-One of the major objectives of this project is for gpsd *not to
-require administration* -- under Linux, at least. It autobauds,
-it does protocol discovery, and it's activated by the hotplug
-system. Arranging these things involved quite a lot of work,
-and we're not willing to lose the zero-configuration property
-that work gained us.
-
-Instead of adding a command-line option to support whatever feature
-you had in mind, try to figure out a way that the feature can
-autoconfigure itself by doing runtime checks. If you're not clever
-enough to manage that, consider whether your feature control might be
-implemented with an extension to the gpsd protocol or the
-control-socket command set.
-
-Here are three specific reasons command-line switches are evil:
-
-(1) Command-line switches are often a lazy programmer's way out of
-writing correct adaptive logic. This is why we keep rejecting
-requests for a baud-rate switch and a GPS type switch -- the *right*
-thing is to make the packet-sniffer work better, and if we relented in
-our opposition the pressure to get that right would disappear.
-Suddenly we'd be back to end-users having to fiddle with settings the
-software ought to figure out for itself, which is unacceptable.
-
-(2) Command-line switches without corresponding protocol commands
-pin the daemon's behavior for its entire lifespan. Why should the user
-have to fix a policy at startup time and never get to change his/her
-mind afterwards? Stupid design...
-
-(3) The command-line switches used for a normal gpsd startup can only
-be changed by modifying the hotplug script. Requiring end-users to
-modify hotplug scripts (or anything else in admin space) is a crash
-landing.
-
-*** Don't use malloc!
-
-The best way to avoid having dynamic-memory allocation problems is
-not to use malloc/free at all. The gpsd daemon doesn't (though the
-client-side code does). Thus, even the longest-running instance
-can't have memory leaks. The only cost for this turned out to be
-embedding a PATH_MAX-sized buffer in the gpsd.h structure.
-
-Don't undo this by using malloc/free in a driver or anywhere else.
-
-** Understanding the code
-
-*** Debugging
-
-For debugging purposes, it may be helpful to configure with --disable-shared.
-This turns off all the shared-library crud, making it somewhat easier to
-use gdb.
-
-There is a script called logextract in the distribution that you can use
-to strip clean NMEA out of the log files produced by gpsd. This can be
-useful if someone ships you a log that they allege caused gpsd to
-misbehave.
-
-gpsfake enables you to repeatedly feed a packet sequence to a gpsd
-instance running as non-root. Watching such a session with gdb should
-smoke out any repeatable bug pretty quickly.
-
-The parsing of GPGSV sentences in the NMEA driver has been a
-persistent and nasty trouble spot, causing more buffer overruns and
-weird secondary damage than all the rest of the code put together.
-Any time you get a bug report that seems to afflict NMEA devices
-only, suspicion should focus here.
-
-*** Profiling
-
-There is a barely-documented Z command in the daemon will cause it to emit
-a $ clause on every request. The $ clause contains four
-space-separated fields:
-
-(1) An identifing sentence tag.
-
-(2) The character length of the sentence containing the timestamp data.
-
-(3) The timestamp associated with the sentence, in seconds since
- the Unix epoch (this time *is* leap-second corrected, like UTC).
- This timestamp may be zero. If nonzero, it is the base time for
- the packet.
-
-(4) An offset from the timestamp telling when gpsd believes the
- transmission of the current packet started (this is actually
- recorded just before the first read of the new packet). If
- the sentence timestamp was zero, this offset is a full timestamp
- and the base time of the packet.
-
-(5) An offset from the base time telling when gpsd received the last
- bytes of the packet.
-
-(6) An offset from the base time telling when gpsd decoded the data.
-
-(7) An offset from the base time taken just before encoding the
- response -- effectively, when gpsd was polled to transmit the data.
-
-(8) An offset from the base time telling when gpsd transmitted
- the data.
-
-The Z figures measure components of the latency between the GPS's time
-measurement and when the sentence data became available to the
-client. For it to be meaningful, the GPS has to ship timestamps with
-sub-second precision. SiRF-II and Evermore chipsets ship times with
-millisecond resolution. Your machine's time reference must also be
-accurate to subsecond precision; I recommend using ntpd, which will
-normally give you about 15 microseconds precision (two orders of
-magnitude better than GPSes report).
-
-Note, some inaccuracy is introduced into the start- and end-of-packet
-timestamps by the fact that the last read of a packet may grab a few
-bytes of the next one.
-
-The distribution lincludes a Python script, gpsprof, that uses the
-Z command to collect profiling information from a running GPS instance.
-You can use this to measure the latency at each stage -- GPS to daemon,
-daemon to client library -- and to estimate the portion of the latency
-induced by serial transmit time. The gpsprof script creates latency
-plots using gnuplot(1). It can also report the raw data.
-
-*** Porting to weird machines: endianness, width, and signedness issues.
-
-The gpsd code is well-tested on 32- and 64-bit IA chips, also on PPCs.
-Thus, it's known to work on mainstream chips of either 32 or 64 bits
-and either big-endian or little-endian representation with IEE754
-floating point.
-
-Handling of NMEA devices should not be sensitive to the machine's
-internal numeric representations, However, because the binary-protocol
-drivers have to mine bytes out of the incoming packets and mung them
-into fixed-width integer quantities, there could potentially be issues
-on weird machines. The regression test should spot these.
-
-If you are porting to a true 16-bit machine, or something else with
-an unusual set of data type widths, take a look at bits.h. We've
-tried to collect all the architecture dependencies here. If splint
-gives you warnings, it is possible you may need to adjust the -D
-directives in .splintrc that are used to define away fixed-width typedefs.
-
-(No, we don't know why splint doesn't handle these natively.)
-
-*** Architecture and how to hack it
-
-gpsd is not a complicated piece of code. Essentially, it spins in a loop
-polling for input from one of three sources:
-
-1) A client making requests over a TCP/IP port.
-
-2) A set of GPSes, connected via serial or USB devices.
-
-3) A DGPS server issuing periodic differential-GPS updates.
-
-The daemon only connects to a GPS when clients are connected to it.
-Otherwise all GPS devices are closed and the daemon is quiescent, but
-retains fix and timestamp data from the last active period.
-
-All writes to client sockets go through throttled_write().
-This code addresses two cases. First, client has dropped the connection.
-Second, client is connected but not picking up data and our buffers are
-backing up. If we let this continue, the write buffers will fill and
-the effect will be denial-of-service to clients that are better behaved.
-
-Our strategy is brutally simple and takes advantage of the fact that
-GPS data has a short shelf life. If the client doesn't pick it up
-within a few minutes, it's probably not useful to that client. So if
-data is backing up to a client, drop that client. That's why we set
-the client socket to nonblocking.
-
-GPS input updates an internal data structure which has slots in it for
-all the data you can get from a GPS. Client commands mine that
-structure and ship reports up the socket to the client. DGPS data is
-passed through, raw, to the GPS.
-
-The trickiest part of the code is the handling of input sources in gpsd.c
-itself. It had to tolerate clients connecting and disconnecting at random
-times, and the GPS being unplugged and replugged, without leaking file
-descriptors; also arrange for the GPS to be open when and only when clients
-are active.
-
-*** Autoconfiguration
-
-One of the design goals for gpsd is to be as near zero-configuration
-as possible. Under most circumstances, it doesn't require either
-the GPS type or the serial-line parameters to connect to it to be
-specified. Presently, here's how the autoconfig works.
-
-1. At each baud rate gpsd grabs packets until it sees either a
- well-formed and checksum-verified NMEA packet, a well-formed and
- checksum-verified packet of one of the binary protocols, or it sees
- one of the two special trigger strings EARTHA or ASTRAL, or it
- fills a long buffer with garbage (in which case it steps to the
- next baud rate).
-
-2. If it finds a SiRF packet, it queries the chip for firmware
- version. If the version is < 231.000 it drops back to SiRF NMEA.
- We're done.
-
-3. If it finds a Zodiac binary packet (led with 0xff 0x81), it
- switches to the Zodiac driver. We're done.
-
-4. If it finds an Evermore binary packet (led with DEL=0x10 followed
- by STX=0x02) it switches to Evermore binary protocol. We're done.
-
-5. If it finds a TSIP binary packet (led with 0x10=DLE), it
- switches to the TSIP driver. We're done.
-
-6. If it finds n iTrax binary packet (led with <* ), it
- switches to the iTrax driver. We're done.
-
-7. If it finds EARTHA, it selects the Earthmade driver, which then
- flips the connection to Zodiac binary mode. We're done.
-
-8. If it finds ASTRAL, it feeds the TripMate on the other end what
- it wants and goes to Tripmate NMEA mode. We're done.
-
-9. If it finds a NMEA packet, it selects the NMEA driver. This
- initializes by shipping all vendor-specific initialization strings
- to the device. The objectives are to enable GSA, disable GLL, and
- disable VTG. Probe strings go here too, like the one that turns
- on SiRF debugging output in order to detect SiRF chips.
-
-10. Now gpsd reads NMEA packets. If it sees a driver trigger string it
- invokes the matching driver. Presently there is really only one of
- these: "$Ack Input 105.\r\n", the response to the SiRF probe. On
- seeing this, gpsd switches from NMEA to SiRF binary mode, probes
- for firmware version, and either stays in binary or drops back
- to SiRF NMEA.
-
-The outcome is that we know exactly what we're looking at, without any
-driver-type or baud rate options.
-
-*** Error modeling
-
-To estimate errors (which we must do if the GPS isn't nice and reports
-them in meters with a documented confidence interval), we need to
-multiply an estimate of User Equivalent Range Error (UERE) by the
-appropriate dilution factor,
-
-The UERE estimate is usually computed as the square root of the sum of
-the squares of individual error estimates from a physical model. The
-following is a representative physical error model for satellite range
-measurements:
-
-From R.B Langley's 1997 "The GPS error budget".
-GPS World , Vol. 8, No. 3, pp. 51-56
-
-Atmospheric error -- ionosphere 7.0m
-Atmospheric error -- troposphere 0.7m
-Clock and ephemeris error 3.6m
-Receiver noise 1.5m
-Multipath effect 1.2m
-
-From Hoffmann-Wellenhof et al. (1997), "GPS: Theory and Practice", 4th
-Ed., Springer.
-
-Code range noise (C/A) 0.3m
-Code range noise (P-code) 0.03m
-Phase range 0.005m
-
-We're assuming these are 2-sigma error ranges. This needs to
-be checked in the sources. If they're 1-sigma the resulting UEREs
-need to be doubled.
-
-See http://www.seismo.berkeley.edu/~battag/GAMITwrkshp/lecturenotes/unit1/
-for discussion.
-
-Carl Carter of SiRF says: "Ionospheric error is typically corrected for
-at least in large part, by receivers applying the Klobuchar model using
-data supplied in the navigation message (subframe 4, page 18, Ionospheric
-and UTC data). As a result, its effect is closer to that of the
-troposphere, amounting to the residual between real error and corrections.
-
-"Multipath effect is dramatically variable, ranging from near 0 in
-good conditions (for example, our roof-mounted antenna with few if any
-multipath sources within any reasonable range) to hundreds of meters in
-tough conditions like urban canyons. Picking a number to use for that
-is, at any instant, a guess."
-
-"Using Hoffman-Wellenhoff is fine, but you can't use all 3 values.
-You need to use one at a time, depending on what you are using for
-range measurements. For example, our receiver only uses the C/A
-code, never the P code, so the 0.03 value does not apply. But once
-we lock onto the carrier phase, we gradually apply that as a
-smoothing on our C/A code, so we gradually shift from pure C/A code
-to nearly pure carrier phase. Rather than applying both C/A and
-carrier phase, you need to determine how long we have been using
-the carrier smoothing and use a blend of the two."
-
-On Carl's advice we would apply tropospheric error twice, and use
-the largest Wellenhof figure:
-
-UERE = sqrt(0.7^2 + 0.7^2 + 3.6^2 + 1.5^2 + 1.2^2 + 0.3^2) = 4.1
-
-DGPS corrects for atmospheric distortion, ephemeris error, and satellite/
-receiver clock error. Thus:
-
-UERE = sqrt(1.5^2 + 1.2^2 + 0.3^2) = 1.8
-
-which we round up to 2 (95% confidence).
-
-Due to multipath uncertainty, Carl says 4.1 is too low and recommends
-a non-DGPS UERE estimate of 8 (95% confidence). That's what we use.
-
-** Known trouble spots
-
-*** The Y2.1K problem and other calendar issues
-
-Because of limitations in various GPS protocols (e.g., they were
-designed by fools who weren't looking past the ends of their noses)
-this code unavoidably includes some assumptions that will turn around
-and bite on various future dates.
-
-The two specific problems are:
-
-1) NMEA delivers only two-digit years.
-
-2) SiRF chips at firmware level 231 deliver only GPS time in binary mode,
-not leap-second-corrected UTC.
-
-See the timebase.h file for various constants that will need to
-be tweaked accasionally to cope with these problems.
-
-Note that gpsd does not rely on the system clock in any way. This
-is so you can use it to set the system clock.
-
-*** Hotplug interface problems
-
-The hotplug interface works pretty nicely for telling gpsd which
-device to look at, at least on my FC3/FC4/FC5 Linux machines. The fly
-in the ointment is that we're using a deprecated version of the
-interface, the old-style /etc/hotplug version with usermap files.
-
-It is unlikely this interface will be dropped by distro makers any
-time soon, because it's supporting a bunch of popular USB cameras.
-Still, it would be nice not to be using a deprecated interface.
-
-I tried moving to the new-style /etc/hotplug.d interface, but I ran
-into a nasty race condition. My hotplug agent got woken up on a USB
-add event as it should, but in the new interface the creation of
-/dev/ttyUSB* can be delayed arbitrarily long after the wakeup event.
-Thus, it may not be there when gpsd goes to probe it unless I
-busy-wait in the script.
-
-There is experimental udev support in the distribution now. Someday
-this will replace the hotplug stuff.
-
-A more general problem: the hotplug code we have is Linux-specific.
-OpenBSD (at least) features a hotplug daemon with similar
-capabilities. We ought to do the riht thing there as well.
-
-*** Security Issues
-
-Between versions 2.16 and 2.20, hotplugging was handled in the most
-obvious way, by allowing the F command to declare new GPS devices for
-gpsd to look at. Because gpsd runs as root, this had problems:
-
-1) A malicious client with non-root access on the host could use F to
-point gpsd at a spoof GPS that was actually a pty feeding bogus
-location data.
-
-2) A malicious client could use repeated probes of a target tty or
-other device to cause data loss to other users. This is a potential
-remote exploit! Not too bad if the bytes he steals are your mouse, it
-would just get jumpy and jerky -- but suppose they're from an actual
-tty and sections drop out of a serial data stream you were relying on?
-
-The conclusion was inescapable. Switching among and probing devices
-that gpsd already knows about can be an unprivileged operation, but
-editing gpsd's device list must be privileged. Hotplug scripts
-should be able to do it, but ordinary clients should not.
-
-Adding an authentication mechanism was considered and rejected (can you
-say "can of big wriggly worms"?). Instead, there is a separate
-control channel for the daemon, only locally accessible, only
-recognizing "add device" and "remove device" commands.
-
-The channel is a Unix-domain socket owned by root, so it has
-file-system protection bits. An intruder would need root permissions
-to get at it, in which case you'd have much bigger problems than a
-spoofed GPS.
-
-More generally, certainly gpsd needs to treat command input as
-untrusted and for safety's sake should treat GPS data as untrusted
-too (in particular this means never assuming that either source won't
-try to overflow a buffer).
-
-Daemon versions after 2.21 drop privileges after startup, setting UID
-to "nobody" and GID to whichever group owns the GPS device specified
-at startup time -- or, if it doesn't exist, the system's
-lowest-numbered TTY device named in PROTO_TTY. It may be necessary to
-change PROTO_TTY in gpsd.c for non-Linux systems.
-
-** Adding new GPS types
-
-This section explains the conventions drivers for new devices should follow.
-
-*** Driver architecture
-
-Internally, gpsd supports multiple GPS types. All are represented by
-driver method tables; the main loop knows nothing about the driver
-methods except when to call them. At any given time one driver is
-active; by default it's the NMEA one.
-
-To add a new device, populate another driver structure and add it to
-the null-terminated array in drivers.c.
-
-Unless your driver is a nearly trivial variant on an existing one,
-it should live in its own C source file named after the driver type.
-Add it to the libgps_c_sources name list in Makefile.am
-
-The easiest way write a driver is probably to copy the driver_proto.c
-file in the source distribution, change names appropriately, and write
-the guts of the analyzer and writer functions. Look in gpsutils.c
-before you do; driver helper functions live there. Also read some
-existing drivers for clues.
-
-*** When not to add a driver
-
-It is not necessary to add a driver just because your NMEA GPS wants
-some funky initialization string. Simply ship the string in the
-initializer for the default NMEA driver. Because vendor control
-strings live in vendor-specific namespaces (PSRF for SiRF, PGRM for
-Garmin, etc.) your initializing control string will almost certainly
-be ignored by anything not specifically watching for it.
-
-*** Initializing time and date
-
-Some mode-changing commands have time field that initializes the GPS
-clock. If the designers were smart, they included a control bit that
-allows the GPS to retain its clock value (and previous fix, if any)
-and for you to leave those fields empty (sometimes this is called "hot
-start").
-
-If the GPS-Week/TOW fields are required, as on the Evermore chip,
-don't just zero them. GPSes do eventually converge on the correct
-time when they've exchanged handshakes with enough satellites, but the
-time required for convergence is proportional to how far off the
-initial value is. So make a point of getting the GPS week right.
-
-*** How drivers are invoked
-
-Drivers are invoked in one of three ways: (1) when the NMEA driver
-notices a trigger string associated with another driver. (2) when the
-packet state machine in packet.c recognizes a special packet type, or
-(3) when a probe function returns true during device open.
-
-Each driver may have a trigger string that the NMEA interpreter
-watches for. When that string is recognized at the start of a
-line, the interpreter switches to its driver.
-
-When a driver switch takes place, the old driver's wrapup method is
-called. Then the new driver's initializer method is called.
-
-A good thing to send from the NMEA initializer is probe strings. These are
-strings which should elicit an identifying response from the GPS that
-you can use as a trigger string for a native-mode driver.
-
-Don't worry about probe strings messing up GPSes they aren't meant for.
-In general, all GPSes have rather rigidly defined packet formats with
-checksums. Thus, for this probe to look legal in a different binary
-command set, not only would the prefix and any suffix characters have
-to match, but the checksum algorithm would have to be identical.
-
-Incoming characters from the GPS device are gathered into packets
-by an elaborate state machine in packet.c. The purpose of this
-state machine is so gpsd can autobaud and recignize GPS types
-automatically. The other way for a driver to be invoked is for
-the state machine to recognize a special packet type associated
-with the driver.
-
-If you have to add a new packet type to packet.c, add tests for the
-type to the TESTMAIN code. Also, remember to tell gpsfake how to
-gather the new packet type so it can handle logs for regression
-testing. The relevant function in gpsfake is packet_get(). It
-doesn't have to deal with garbage or verify checksums, as we assume
-the logfiles will be clean packet sequences,
-
-Probe functions are interpreted for drivers that don't use the packet
-getter because they read from a device with special kernel support.
-See the Garmin binary driver for an example.
-
-*** Where to put the data you get from the GPS
-
-Your driver should put new data from each incoming packet or sentence
-in the 'newdata' member of the GPS, and return a validity flag mask
-telling what members were updated. There is driver-independent code
-that will be responsible for merging that new data into the existing
-fix. To assist this, the CYCLE_START_SET flag is special. Set this
-when the driver returns the first timestamped message containing fix
-data in in an update cycle. (This excludes satellite-picture messages
-and messages about GPS status that don't contain fix data.)
-
-Your packet parser must return field-validity mask bits (using the
-_SET macros in gps.h), suitable to be put in session->gpsdata.valid.
-The watcher-mode logic relies on these as its way of knowing what to
-publish. Also, you must ensure that gpsdata.fix.mode is set properly to
-indicate fix validity after each message; the framework code relies on
-this. Finally, you must set gpsdata.status to indicate wheen DGPS
-fixes are available, whether through RTCM or WAAS/Egnos.
-
-Your packet parser is also responsible for setting the tag field
-in the gps_data_t structure. This is the string that will be emitted
-as the first field of each $ record for profiling. The packet getter
-will set the sentence-length for you; it will be raw byte length,
-including both payload and header/trailer bytes.
-
-Note, also, that all the timestamps your driver puts in the session
-structure should be UTC (with leap-second corrections) not just Unix
-seconds since the epoch. The report-generator function for D
-does *not* apply a timezone offset.
-
-*** Report errors with a 95% confidence interval
-
-gpsd drivers are expected to report position error estimates with
-a 95% confidence interval. A few devices (Garmins and Zodiacs)
-actually report error estimates. For the rest we have to compute them
-using an error model.
-
-Here's a table that explains how to convert from various
-confidence interval units you might see in vendor documentation.
-
-sqr(alpha) Probability Notation
------------------------------------------------------------------------
- 1.00 39.4% 1-sigma or standard ellipse
- 1.18 50.0% Circular Error Probable (CEP)
- 1.414 63.2% Distance RMS (DRMS)
- 2.00 86.5% 2 sigma ellipse
- 2.45 95.0% 95% confidence level
- 2.818 98.2% 2DRMS
- 3.00 98.9% 3 sigma ellipse
-------------------------------------------------------------------------
-
-There are constants in gpsd.h for these factors.
-
-*** Log files for regression testing
-
-Any time you add support for a new GPS type, you should also send us a
-representative log for your GPS. This will help ensure that support
-for your device is never broken in any gpsd release, because we will
-run the full regression before we ship.
-
-A logfile should consist of an identifying header followed by a
-straight unencoded dump of GPS data, whether NMEA or binary. The
-header should consist of text lines beginning with # and ending with LF.
-Here is the beginning of one log file I already have:
-
-# Name: Holux GM-210
-# Cycle-time: 1-second
-# Start-of-cycle: ?
-# Pause-noted: ?
-# Well-behaved: N
-# Submitted-by: "Patrick L. McGillan" <pmcgillan@pateri.com>
-# Date: 4 Apr 2005
-$GPGGA,012519.563,4131.7353,N,09336.8150,W,0,00,50.0,280.2,M,-31.6,M,0.0,0000*7D
-$GPGSA,A,1,,,,,,,,,,,,,50.0,50.0,50.0*05
-$GPRMC,012519.563,V,4131.7353,N,09336.8150,W,0.00,,050405,,*14
-$GPGGA,012520.563,4131.7353,N,09336.8150,W,0,00,50.0,280.2,M,-31.6,M,0.0,0000*77
-$GPGSA,A,1,,,,,,,,,,,,,50.0,50.0,50.0*05
-$GPGSV,3,1,09,14,65,034,00,01,55,291,43,25,53,210,37,22,45,125,00*7E
-$GPGSV,3,2,09,30,29,096,00,11,25,294,32,05,20,056,00,18,14,127,00*73
-$GPGSV,3,3,09,15,08,176,00*4C
-$GPRMC,012520.563,V,4131.7353,N,09336.8150,W,0.00,,050405,,*1E
-$GPGGA,012521.563,4131.7353,N,09336.8150,W,0,00,50.0,280.2,M,-31.6,M,0.0,0000*76
-The way to fill in the Name, Cycle-Time, Submitted-by, and Date
-headers should be pretty obvious.
-
-Start-of-cycle should be the name of the NMEA sentence (or, in a
-packet protocol, the numeric type ID of the packet) that is emitted
-first in each cycle.
-
-Pause-Noted should be Y or N as there is or is not a visible pause
-between cycles.
-
-Well-behaved should by Y if all sentences in the same cycle have the
-same timestamp, N otherwise.
-
-New log files should include after Date an additional Location header
-giving the submitter's city, state/province, country code, and a rough
-latitude/longitude. A good one for the above file might look like
-this:
-
-Location: Osceola, Iowa, US, 41N93W
-
-If you have notes or comments on the logfile or the GPS, or any
-additional information you think might be helpful, add them as
-additional # comments (not containing a colon) after these headers.
-The test machinery that interprets the headers will ignore these and
-any empty comment lines.
-
-See the header comment of the gpsfake.py module for more about the
-logfile format.
-
-An ideal log file would include an initial portion during which the
-GPS has no fix, a portion during which it has a fix but is stationary,
-and a portion during which it is moving.
-
-If your GPS is SiRF-based, it's easy to capture packets using the
-'l' command of sirfmon.
-
-*** Throughput computation for baud rate changes
-
-At low baud rates it is possible to try to push more characters of
-NMEA through per cycle than the time to transmit will allow. Here
-are the maxima to use for computation:
-
-GLL 51
-GGA 82
-VTG 40
-RMC 75
-GSA 67
-GSV 60 (per line, thus 180 for a set of 3)
-ZDA 34
-
-The transmit time for a cycle (which must be less than 1 second)
-is the total character count multiplied by 10 and divided by the
-baud rate.
-
-A typical budget is GGA, RMC, GSA, 3*GSV = 82+75+67+(3*60) = 404.
-
-When you write a driver that includes the capability to change
-sampling rates, you must fill in the cycle_chars member with
-a maximum character length so the daemon framework code will
-be able to compute when a sample-rate change will work. If
-you have to estimate this number, err on the high side.
-
-** The buffering problem
-
-Considered in the abstract, the cleanest thing for a
-position/velocity/time oracle to return is a 14-tuple including
-position components in all four dimensions, velocity in three, and
-associated error estimates for all seven degrees of freedom. This is
-what the O message in GPSD protocol attempts to deliver.
-
-If GPS hardware were ideally designed, we'd get exactly one report
-like this per cycle from our device. That's what we get from SiRF-II
-protocol (all PVT data is in packet type 02), with the Zodiac protocol
-(all PVT data is in the type 1000 packet), and from Garmin's
-binary-packet protocol. These, together, account for a share of the
-GPS market that is 80% and rising in 2006.
-
-Unfortunately, many GPSes actually deliver their PVT reports as a
-collection of sentences in NMEA 0183 (or as packets in a vendor binary
-protocol less well designed than SiRF's) each of which is only a
-partial report. Here's the most important kind of incompleteness: for
-historical reasons, NMEA splits 2-D position info and altitude into
-two different messages (GGA and GPRMC or GLL), each issued once during
-the normal 1-second send cycle.
-
-*** Mapping the design space
-
-For NMEA devices, then (and for devices speaking similary mal-designed
-vendor binary protocols) accumulating a complete PVT thus requires
-decisions about the following sorts of actions:
-
-1. What data will be buffered, and for how long.
-
-2. When the accumulated data will be shipped to the user.
-
-3. When to invalidate some or all of the buffered data.
-
-The when-to-ship question assumes watcher mode is on; if the user
-queries explicitly the when-to-ship decision is out of our hands.
-
-In thinking about these decisions, it's useful to consider the set of
-events on which an action like "merge new data into PVT buffer" or
-"clear the PVT data buffer" or "ship report to user" can trigger.
-
-1. On receipt of any sentence or packet from the GPS.
-
-2. On receipt of a specified sentence or packet from the GPS.
-
-3. When the timestamp of a sentence or packet differs from the
- last timestamp recorded.
-
-4. When some or all of the PVT data has not been refreshed for a
- specified number of seconds.
-
-That latency can really matter. If the GPS is on a car driving down
-the highway at 112kph (70mph), the 1 second delay in the buffered data
-can represent an error of 31 meters (102 feet) in reported position.
-
-In general, buffering would make it easy to retrieve the data you want
-at the time you want it, but the data would not necessarily be valid
-for time of retrieval. Buffering makes life easier for applications that
-just want to display a position indicator, and harder for
-perfectionists that worry about precise location of moving GPSes.
-
-The policy decision about whether you want to be a "perfectionist" or
-not fundamentally belongs in the client. This isn't to say gpsd could
-not have different buffering modes to help the client implement its
-decision, but the modes and their controls would have to be
-implemented *very* carefully. Otherwise we'd risk imposing the wrong
-policy (or, worse, a *broken version* of a wrong policy) on half the
-client applications out there.
-
-There are hundreds, even thousands of possible sets of action-to-event
-bindings. The "right" binding for a particular device depends not
-only on the protocol it uses but on considerations like how much time
-latency we are willing to let the buffering policy inflict on a
-report.
-
-Discussion of possible policies follows. See also the speculation
-later on about combining buffering with interpolation.
-
-**** Report then clear per packet
-
-A device like a SiRF-II that reports all its PVT data in a single
-packet needs no buffering; it should ship to the user on receipt of
-that packet and then invalidate the PVT buffer right afterwards.
-(This is a "report then clear per packet" policy.)
-
-But triggering a buffer clear on every packet would do bad things if
-we're in client-pull mode. We never know when a client might ask for a
-response. Consider the case of two simultaneously connected clients,
-one sending queries and the other in watcher mode - if we clear after
-we ship the O message to the watcher, then the other client queries,
-it gets nothing in response.
-
-**** Buffer all, report then clear on trigger
-
-On the other hand, if (say) we knew that an NMEA GPS were always going
-to end its report cycle with GPGGA, it might make sense to buffer
-all data until GPGGA appears, ship a report afterwards, and then
-clear the PVT buffer. This would mean shipping just one report
-per cycle (good) at the cost of introducing some latency into the
-reporting of data the GPS sends earlier in the cycle (bad). (This
-would be "buffer all, report-then-clear on trigger")
-
-Here's where it gets ugly. We don't know what the user's tolerance
-for latency is. And, in general, we can't tell when end-of-cycle, is
-happening, because different NMEA devices ship their sentences in
-different orders. Worse: we can't even count on all send cycles of
-the same device having the same end sentence, so the naive plan of
-waiting one cycle to see what the end sentence is won't work. Devices
-like the Garmin 48 have two different cycle sequences with different
-start and end sentences.
-
-So we can't actually trigger on end-of-cycle. The only between-cycles
-transition we can spot more or less reliably is actually *start* of
-cycle, by looking to see when the timestamp of a sentence or packet
-differs from the last timestamp recorded (event 3 above). This will
-be after the last end-of-cycle by some (possibly large) fraction of a
-second; in fact, waiting for start-of-cycle to report data from the
-last one is the worst possible latency hit.
-
-**** Buffer all, report on every packet, clear at start-of-cycle
-
-Another possible policy is "buffer all, report on every packet, clear
-at start-of-cycle". This is simple and adds minimum reporting
-latency to new data, but means that O responses can issue more than once per
-second with accumulating sets of data that only sum up to a complete
-report on the last one.
-
-Another advantage of this policy is that when applied to a device like
-a SiRF-II or Zodiac chipset that ships only one PVT packet per cycle,
-it collapses to "report then clear per packet".
-
-Here's a disadvantage: the client display, unless its does its own
-buffering, may flicker annoyingly. The problem is this: suppose we
-get an altitude in a GGA packet, throw an O response at the client,
-and display it. This happens to be late in the report cycle. Start
-of cycle clears the buffer; a GPRMC arrives with no altitude in it.
-The altitude value in the client display flickers to "not available",
-and won't be restored until the following GGA.
-
-This is the policy gpsd currently follows.
-
-**** Buffer all, report on every packet, never clear data
-
-Has all the advantages of the previous policy and avoids the flicker
-problem. However, it would mean the user often sees data that is up to one
-cycle time stale. This might be OK except that it could happen even if
-the GPS has just lost lock -- that is, in the interval between start
-of cycle and receipt of sentence with the mode field invalidating the,
-bad data, gpsd would be pretending to know something it doesn't.
-
-GPSes sometimes do this, delivering data from dead-reckoning or
-interpolation when they've lost lock. This comes up most often with
-altitude; because of the tall skinny shape of the tetrahedra defined
-by GPS range data, a GPS can lose 3D lock but still have an altitude
-guess good enough for it to deliver a 2D fix with confidence. But
-just because GPSes fudge is no good reason for gpsd to add a layer of
-prevarication on top of that.
-
-But the conclusive argument against this policy is that, while it can be
-simulated by buffering data delivered according to a clear-every-cycle
-policy, the reverse is not true. Under this policy there would be
-no way to distinguish in gpsd's reports between data valid now and
-data held over from a previous cycle; on the other hand, under
-a clear-at-start-of-cycle policy the client can still do whatever
-buffering and smoothing it wants to.
-
-**** Buffer all, report on every packet, time out old data
-
-gpsd does not presently keep the sort of per-field ageing data needed
-to track the age of different PVT fields separately. But it does know
-how many seconds have elapsed since the last packet receipt -- it uses
-this to tell if the device has dropped offline, by looking for an age
-greater than the cycle time.
-
-When the device is returning fixes steadily, this policy will look
-exactly like "buffer all, report on every packet, never clear data",
-because every piece of data will be refreshed once per cycle. It will
-have the same sort of prevarication problems as that policy, too. If
-the device loses lock, the user will see that the PVT data is
-undefined only when the timeout expires.
-
-Fine-grained timeouts using per-field aging wouldn't change this
-picture much. They'd mainly be useful for matching the timeout
-on a piece of data to its "natural" lifetime -- usually 1 sec for
-PVT data and 5 sec for satellite-picture data.
-
-*** There is no perfect option
-
-Any potential data-management policy would have drawbacks for some
-devices even if it were implemented perfectly. The more complex
-policies would have an additional problem; buffering code with
-complicated flush triggers is notoriously prone to grow bugs near its
-edge cases.
-
-Thus, gpsd has a serious, gnarly data-management problem at its core.
-This problem lurks behind many user bug reports and motivates some of
-the most difficult-to-understand code in the daemon. And when you
-look hard at the problems posed by the variable sequences of sentences
-in NMEA devices...it gets even nastier.
-
-It's tempting to think that, if we knew the device type in advance,
-we could write a state machine adapted to its sentence sequence that
-would do a perfect job of data management. The trouble with this
-theory is that we'd need separate state machines for each NMEA
-dialect. That way lies madness -- and an inability to cope gracefully
-with devices never seen before. Since the zero-configuration design
-goal means that we can't count on the user or administrator passing
-device-type information to gpsd in the first place, we avoid this trap.
-
-But that means gpsd has to adapt to what it sees coming down the wire.
-At least it can use a different policy for each device driver,
-dispatching once the device type has been identified.
-
-*** Combining buffering with interpolation: a speculative design
-
-One possible choice (not let implemented in gpsd or its client
-libraries) would be to combine buffering with interpolation. Here's a
-speculative design for a client which does its own extrapolation:
-
-Thread 1: GPS handler. Sets watcher mode. Each time a report is
-received, it stores that data along with the result of a call to
-gettimeofday() (so that we have microsecond precision, rather than
-just seconds from time()). No need to double-buffer any data - just the
-latest complete O report is sufficient. When the client receives a query
-from thread 2, it applies a differential correction to the last
-reported position, based on the last reported velocity and the
-difference between the stored gettimeofday() time and a new
-gettimeofday() call.
-
-Thread 2: main application. Driven by whatever events you want it
-to be. Queries thread 1 whenever it needs an accurate GPS position
-NOW.
-
-The main problem with this approach is that it would require an
-onboard clock far more accurate than the GPS's once-per-second
-reports. This is a problem; in general, we can't assume that
-a gpsd instance running in a car or boat will have access to
-ntpd or NIST radio time signals.
-
-** Blind alleys
-
-Things we've considered doing and rejected.
-
-*** Reporting fix data only once per cycle
-
-See the discussion of the buffering problem, above. The "Buffer all,
-report then clear on start-of-cycle" policy would introduce an
-unpleasant amount of latency. gpsd actually uses the "Buffer all,
-report on every packet, clear at start-of-cycle" policy.
-
-*** Allowing clients to ship arbitrary control strings to a GPS
-
-Tempting -- it would allow us to do sirfmon-like things with the
-daemon running -- but a bad idea. It would make denial-of-service
-attacks on applications using the GPS far too easy. For example,
-suppose the control string were a baud-rate change?
-
-*** Using libusb to do USB device discovery
-
-There has been some consideration of going to the cross-platform libusb
-library to do USB device discovery. This would create an external
-dependency that gpsd doesn't now have, and bring more complexity on
-board than is probably desirable.
-
-We've chosen instead to rely on the local hotplug system. That way
-gosd can concentrate solely on knowing about GPSes.
-
-*** Setting FIFO threshold to 1 to reduce jitter in serial-message times
-
-When using gpsd as a time reference, one of the things we'd like to do
-is make the amount of lag in the message path from GPS to GPS small
-and with as little jitter as possible, so we can correct for it with
-a constant offset.
-
-A possibility we considered is to set the FIFO threshold on the serial
-device UART to 1 using TIOCGSERIAL/TIOCSSERIAL. This would, in
-effect, disable transmission buffering, increasing lag but decreasing
-jitter.
-
-But it's almost certainly not worth the work. Rob Janssen, our timekeeping
-expert, reckons that at 4800bps the UART buffering can cause at most
-about 15msec of jitter. This is, observably, swamped by other less
-controllable sources of variation.
-
-Local variables:
-mode: outline
-paragraph-separate: "[ ]*$"
-end: