path: root/HACKING

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.

If you're looking for things to hack on, first see the TODO file.

** Contribution guidelines

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.

If you are introducing a new feature, include a documentation patch.

If you are contributing a driver for a new GPS, please also do the
following things:

1) Send us a representative sample of the GPS output for future 
   regression-testing.

2) 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.

Before shipping a patch, it is a good idea to make sure the patched
code displays no warnings when you run 'make splint'.  See
http://www.splint.org for a description of this tool.

Also, use the regression-test suite -- "make testregress" -- to check
that your patch doesn't break the handling of any already-supported GPS.

** 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.).

** 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.

** 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 problms 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.

** 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, type 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.

The function is_input_waiting() is not strictly necessary for the most
important use of the low-level interface, which is when it gets called
from the daemon mainline.  In that context, FD_ISSET() on the element
of the file-descriptor set representing the GPS would tell us if there
were input waiting.  The explicit test is there for other programs
that might call gps_poll() without such a guarantee.

** 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.

** 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 SiRF packet, a well-formed and checksum-verified
   Zodiac packet, 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 a TSIP binary packet (led with 0x10=DLE), it
   switches to the TSIP driver.  We're done.

5. If it finds EARTHA, it selects the Earthmade driver, which then
   flips the connection to Zodiac binary mode.  We're done.

6. If it finds ASTRAL, it feeds the TripMate on the other end what
   it wants and goes to Tripmate NMEA mode.  We're done.

7. 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.

8. 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.

** Don't add 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.

** Error modeling

To estimate errors (which we must do if the GPS isn't nice like a
Garmin and reports them in meters), 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 1-sigma error ranges. This needs to
be checked in the sources.

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.

Due to multipath uncertainty, Carl says 4.1 is too low and recommends
a non-DGPS UERE estimate of 8.  That's what we use.

** Adding new GPS types

Almost all GPSes speak NMEA 0183.  However, it may occasionally be necessary
to add support for some odd binary format.  We're told that the hex dump
functions in CuteCom <http://cutecom.sourceforge.net/> can be useful for
investigating such protocols.

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 list.

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 GPS status indications.)

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.  The new driver 
initializer method is called immediately. 

Note: it is not necessary to add a driver just because your 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.

Another 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 driver.  This is
how we detect SiRF chips (see step 5 under autoconfiguration above).

If you're writing a driver, look in gpsutils.c; driver helper
functions live there.  The easiest way is probably to copy an
existing driver and change the guts of the analyzer function.

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.

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.

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,

** 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.

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.

** Blind alleys

Things we've considered doing and rejected.

*** Accumulating fix data across an entire cycle

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.

Unfortunately GPS protocols are, in general, rather badly designed for
approximating this.  For historical reasons, NMEA splits 2-D position
info and altitude in two different messages, each issued once
during the normal 1-second send cycle.  Some vendor binary
protocols have similar problems.

This means that gpsd may execute one of two policies.  Either it
must issue a separate report on each sentence or packet containing PVT
information, or it must accumulate data across an entire send cycle
and issue a unified report at end of cycle.  Report-per-packet is
simpler, and adds minimum reporting latency, but means that O
responses may issue more than once per second with complementary
sets of data that add up to a complete report.  The accumulating
policy means there will be exactly one report per cycle and it will
contain full PVT information, but it may have additional latency
of up to one second.

Presently gpsd implements mainly report-per-packet, with a limited
exception for 2D fix data (not cleared until a mode change invalidates
it).  This works well with the SiRF protocol (all PVT data is in
packet type 02) and with the Zodiac protocol (all PVT data is in the
type 1000 packet).  These, together, account for a share of the GPS
market that is 80% and rising in 2005.  It works less well with
generic NMEA devices.

The reason we have not attempted a fully accumulating policy is that it
would require gpsd to know which sentences start and end the GPS send
cycle is, so as to know when to ship the accumulated data to the
client and clear the buffers.  Which sentence this is does, in fact,
vary across GPS types. One of gpsd's design goals, zero configuration,
means that we can't count on the user or administrator passing gpsd
this information; instead, gpsd must somehow be able to autodetect it.

This turns out to be hard. We can get timestamps from some (though not
all) NMEA sentences, but there are some GPSes that change the timestamp
during the send cycle as well as at start and end.  Thus, we can't
use coincidence of timestamps to map the cycle.

We can't even count on all send cycles of the same device looking the
same.  Many GPSes only send GSV when they have satellite lock.
Without knowing the GPS type in advance, it isn't predictable where in
the send cycle the GSV will be emitted.

Thus, the only information we have to go on is the wall-clock timing
of the sentences in the send cycle.  The feature we need to look for
is the inter-cycle pause.  And the first problem is that at some
speeds, with some devices, there isn't one.  In particular, at 4800bps
on an NMEA device sending GGA/RMC/VTG/GLL/GSA/GSV, the intercycle
pause is nonexistent or too small to be detectible.  See the first
graph in the paper on GPS latency profiling at
<http://gpsd.berlios.de/performance.html>. In that one, transmission
times sometimes add to slightly more than a full 1-second cycle,
probably due to instrumentation error; the point is, there is no
significant gap to be detected before the next cycle.

Even if we could rely on that gap to be present, the logic needed to
detect it is of the sort that is notoriously prone to subtle timing
failures.  For example, a system-load-induced stall in the host
operating system's serial layer, happening at the right time shortly
after device open, might masquerade as an intercycle gap, causing gpsd
to lock onto the wrong sentence.

With great effort and ingenuity some of these problems could be at
least partly solved.  Unfortunately, there is every reason to suspect
the resulting code would be complex, brittle and bug-prone.
Presently, it doesn't seem like a good idea for a marginal improvemnt
in 20% of GPSes.

*** 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.

*** Evermore binary protocol

Described at <http://www-ri.hive.no/nmea/GM-X205_UG_revB.pdf>.
Doesn't seem to support any capabilities that NMEA doesn't, other
than shipping TDOP.

Local variables:
mode: outline
paragraph-separate: "[ 	]*$"
end: