1.How To Use This Source Code

1.1 Compile Kernel Source Code and Make it bootable

My work is based on Linux Kernel 3.9.3, and I use following bash shell to compile the kernel:

cd /usr/src/kernels/linux-3.9.3 && 
make bzImage && make modules && 
make modules_install && 
cp /usr/src/kernels/linux-3.9.3/arch/x86/boot/bzImage /boot/vmlinuz-3.9.3lichen && 
mkinitrd -v --force /boot/initrd-3.9.3lichen.img 3.9.3+

Notice: The module group name "3.9.3+" may be differnet in different distributions. For example, this value is "3.9.3" in Debian 7 32-bit and "3.9.3+" in Fedora 17 32-bit. If you have doubt about it, please refer to folder name in /lib/modules/, there will be a folder named by "3.9.3" or "3.9.3+" or something else in it.

Next step, we need to modify the configuration of grub/grub2 to make the system boot using our new kernel. All you need to do is copy and paste one menuentry, then modify the boot image name and initialized ram disk name. Below is an example:

menuentry 'Fedora Linux' --class fedora --class gnu-linux --class gnu --class os $menuentry_id_option 'gnulinux-simple-00f2e2dd-3063-4d2c-8a78-1bd630780958' {
        set gfxpayload=keep
        insmod gzio
        insmod part_msdos
        insmod ext2
        set root='hd0,msdos1'
        if [ x$feature_platform_search_hint = xy ]; then
          search --no-floppy --fs-uuid --set=root --hint-bios=hd0,msdos1 --hint-efi=hd0,msdos1 --hint-baremetal=ahci0,msdos1 --hint='hd0,msdos1'  05e8fabc-a528-4c1e-ba57-3299841a6cb1
          search --no-floppy --fs-uuid --set=root 05e8fabc-a528-4c1e-ba57-3299841a6cb1
        echo    'Loading Linux 3.3.4-5.fc17.i686.PAE ...'
        linux   /vmlinuz-3.3.4-5.fc17.i686.PAE root=UUID=00f2e2dd-3063-4d2c-8a78-1bd630780958 ro SYSFONT=False rd.lvm=0 rd.dm=0 LANG=zh_CN.UTF-8  KEYTABLE=us rd.md=0 rd.luks=0 rhgb quiet 
        echo    'Loading initial ramdisk ...'
        initrd  /initramfs-3.3.4-5.fc17.i686.PAE.img

Just change "vmlinuz-3.3.4-5.fc17.i686.PAE" to "vmlinuz-3.9.3lichen" and "initramfs-3.3.4-5.fc17.i686.PAE.img" to "initrd-3.9.3lichen.img" (you can also change the entry name if you want), it will guide grub to use new kernel for system.

1.2 Compile New Timestamp Library

First step, create object file for modified version of tzcode.
gcc -c tzcode/localtime.c -o localtime.o

Second step, create object file for our timestamp library.
gcc -c timestamp.c -o timestamp.o

Third step, link two objects above and make one shared library.
gcc -shared -o libtimestamp.so localtime.o timestamp.o -lrt

"-lrt" is for functions like "clock_gettime()".

Any user program can use API provided by libtimestamp.so, like "get_new_timestamp()", "convert_to_gps()", and "convert_from_gps()".

Fourth step, compile user program into executable file.
gcc test.c /root/gsoc-lib/libtimestamp.so -o test

1.3 Compile two required time data (tz databse and IERS-A bulletin)

1.3.1 tz databse

I have provided two version of tz database(2006a and 2013d) that enabled leap second support at here, there default target folder is /usr/local/etc/zoneinfo/.v/$version/.

If you want to include more version of tz database, you need to modify the Makefile of corresponding tz data.
  • Make sure TOPDIR is "/usr/local", and change TZDIR into "$(TOPDIR)/etc/zoneinfo/.v/$(VERSION)/"
  • Change REDO to "right_posix", the default value is "posix_right", the compiled tz database will not include leap second information if we leave it as "posix_right"

1.3.2 IERS-A bulletin

For IERS-A bulletin, please use my python compiler to compile a bulletin into required format.

1.4 Use this new timestamp API in user programs

By including header file "timestamp.h" and link with shared library "libtimestamp.so", you can use every function we provided below:

int my_gettimeofday(struct time_struct* ret);
int compare_timestamp(struct time_struct* t1, struct time_struct* t2);
struct time_struct subtract(struct time_struct* ts, f_fp* delta);
struct time_struct add(struct time_struct* ts, f_fp* delta);
f_fp get_offset(struct time_struct* t1, struct time_struct* t2);
int convert_to_gps(struct time_struct* src, struct time_struct* dst);
int convert_from_gps(struct time_struct* src, struct time_struct* dst, u_int32 dst_timescale);
void GetTzVersion(int timescale,char* ret);

If you want to see example, please refer to GSoC2013NewTimestampAndAPITestCases.

2.How Our Project Works

2.1 Timestamp

The current timestamp is generated from "clock_gettime()", which can provide nanosecond resolution. The counts for seconds and nanoseconds are stored in two 64-bit number.

When user calls "my_gettimeofday()", we will call "clock_gettime()", then copy the result to our timestamp. What's more, our "my_gettimeofday()" will obtain expected_offset, expected_error and discontinuity_count from kernel by make syscall, and write these values into timestamp to be returned to user program.

2.2 expected_error

The expected error is calculated by counting how many seconds have passed after last "talking" to trusted time source.

For example, our system has just made adjustment according to time information on pool.ntp.org, and one hour passed, the expected error will be 3600*ratio. "ratio" is a decimal, and its value is set to 1 so far.

Since the computer system may hibernate for a long time, and during this period, only CMOS clock is reliable. I wrote a tiny program to read CMOS clock and compare it to previous value, and calculate out the expected error.

This value will be -1 (undefined) if nobody had ever tried to get expected error, because we don't know its value since the system has just started up.

If you have interest in how to read CMOS in linux kernel, please refer to GSoC2013NewTimestampAndAPIReadRTCInKernel.

2.3 expected_offset

I don't need to care about how system make correction on clock, I just need to provide this variable and a function to modify this value.

Prividing this variable is pretty easy, the question is how to add a syscall in kernel to let programs in user space modify it. And finally I found how to get this done.

  • Modify /arc/x86/syscalls/syscall_32.tbl. Add a syscall entry into it and assign a unused syscall number to it. e.g "352 i386 set_timestamp_offset sys_set_timestamp_offset"
  • Add a definition of new syscall in /include/linux/syscalls.h, you can refer to other syscalls in that file.
  • Write your own function somewhere, by using "SYSCALL_DEFINE" macro. "SYSCALL_DEFINE1" means this syscall only has one argument. "SYSCALL_DEFINE2" means this syscall have two arguments.

2.4 discontinuity_counter

This is a very interesting part, in order to find out where I should place my code in kernel, I examined the function call stack when I use "settimeofday()" and "clock_settime()" in my program.

The result shows that if we call "clock_settime()", Linux kernel will set the wall time according to arguments of it; but if we call "settimeofday()", it will later call "clock_settime()" to set the wall time.

That means I only need to increase my discontinuity counter when "clock_settime()" was called.

Discontinuity counter is a unsigned 32-bit number, maintained in kernel space. Every time user want to set the wall time, it will increase by 1. And every time user calls "my_gettimeofday()" to obtain our new timestamp, the discontinuity counter will be included.

2.5 convert to GPS timescale

2.5.1 UTC to GPS

The biggest problem is that current TZ code and database don't support the coexistence of different version. As a normal user, the latest version will satisfy all requirements.

But for us, we treat different version of TZ databse as different timescale. If we want to to do conversion between two TZ timescale, we need to have all data of these two TZ version.

So I modified several function of the latest TZ code (2013d) to make it support different version of TZ data.

The main changes are:

  • Copy "tzset()" to "my_tzset()", add a argument of version string, i.e "2013d". It will load GMT data into memory for later use.
  • Modify "tzload()", add a argument of version string, If this argument is not NULL, it will look into "/usr/local/etc/zoneinfo/.v/$(VERSION)/" for this version of TZ database, otherwise it will look into "/usr/local/etc/zoneinfo/".
  • Uncomment "leapcorr()", "time2posix()" and "posix2time()", and make them usable. "leapcorr()" is to calculate how many leapsecond is added to UTC time since 1970-1-1 at a given time. It is actually the count of seconds we need to add to UTC timestamp when convert UTC timestamp to GPS timestamp. "time2posix()" and "posix2time()" are two functions that do conversion between GPS and UTC based on "leapcorr()".

In our project, TZ timescale's version is a 32-bit number, which has a form of IP address(x.x.x.x). And its version varies from to, I used - so far, and - is reseved for any previous version.

Since we have timescale indicator number now, we need to figure out a way of mapping timescale version number to TZ databse name (e.g. "2013d" and "2006a"), that's what the function below do:

void GetTzVersion(int timescale,char* ret);

Once we call this function, we will get TZ database name in "char[] ret". Then we can use this TZ database name for "tzset()" or "tzload()".

2.5.2 IERS-A to GPS

Every IERS-A bulletin contains "combined earth orientation parameters" of the past 7 days, and one year's prediction. Each item of IERS-A data has "UT1-UTC" in it, so conversion from IERS-A to GPS is based on that value.

According on public information, UT1-UTC's value is taken on 00:00:00, instead of 24:00:00. That means, if we want to spread the difference of offset(UT1-UTC) all over a day, we need to take next day's UT1-UTC into consideration.

For example, at 2005-12-30 00:00:00(its posix timestamp is 1135900800), the UT1-UTC is -0.661163; at 2005-12-31 00:00:00(its posix timestamp is 1135987200), the UT1-UTC is -0.661145. And we are given a time 2005-12-30 12:00:00(its posix timestamp is 1136030400), the UT1-UTC value at this moment is calculated by "( ((-0.661145) - (-0.661163))/(1135987200 - 1135900800) )*(1136030400-1135900800)". When we get this value, we can subtract it from 1136030400 and get UTC timestamp. Once we get UTC timestamp, we can use the method in 2.5.1 to convert UTC timestamp into GPS timescale.

2.6 convert from GPS timescale

2.6.1 GPS to UTC

This is just the inverse process of conversion from UTC to GPS.

First, our program need to obtain the TZ database name from timescale number.

Second, load TZ database into memory by given database name.

Third, figure out how many leapseconds should be subtracted from the GPS timestamp and do the operation.

Then, we finally get a UTC timestamp in given timescale.

2.6.2 GPS to IERS-A timescale

This is the most challenging part of this project. Because leapsecond brought us a lot of trouble. In order to handle leapsecond when converting a GPS timestamp to IERS-A timescale, I wrote my own compiler which can give the New Timestamp Library a easy-to-use database.

IERS-A bulletin have following data format, for example:
                              IERS Rapid Service                                
              MJD      x    error     y    error   UT1-UTC   error              
                       "      "       "      "        s        s                
    5 12 30  53734  .05486 .00002  .38460 .00003  -.661163  .000008          
    5 12 31  53735  .05378 .00002  .38384 .00002  -.661145  .000009          
    6  1  1  53736  .05269 .00002  .38329 .00003   .338787  .000008          
    6  1  2  53737  .05174 .00002  .38292 .00002   .338545  .000009          
    6  1  3  53738  .05090 .00001  .38266 .00002   .338072  .000009          
    6  1  4  53739  .05015 .00001  .38236 .00003   .337379  .000010          
    6  1  5  53740  .04949 .00001  .38203 .00003   .336476  .000010  

By using the same method in 2.5.2, we can figure out the corresponding UTC time of each item. And here's the problem: how can we create a table that includes the mapping from UTC timestamp to IERS-A timestamp?

The intuitive idea is: just figure out the corresponding UTC time of each IERS-A time(at 00:00:00 each day), and mapping back.

But this solution is not the perfect one. Let me give you an example:

IERS-A time 2005-12-30 00:00:00(1135900800) map to UTC time 2005-12-30 00:00:00.661163(1135900800.661163); IERS-A time 2005-12-31 00:00:00(1135987200) map to UTC time 2005-12-31 00:00:00.661145(1135987200.661145);

So UTC time between (utc_tick_start=1135900800.661163,utc_tick_end=1135987200.661145) will be mapped to IERS-A time (local_tick_start=1135900800,local_tick_end=1135987200)

But how about the day in which a leapsecond is applied ? Like IERS-A time 2006-01-01 00:00:00(1136073600) map to UTC time 2005-12-31 23:59:59.661213 or 2005-12-31 23:59:60.661213, according to whether we take leapsecond into consideration when we get UTC timestamp from GPS timestamp.

If one day have leapsecond to be applied, we consider the count of SI second to be 86401, otherwise the count of SI second is 86400.

Now all parameters we need is ready, the result of IERS-A timestamp is local_tick_start + ( (local_tick_end - local_tick_start) / (count_si_second) ) * ( UTC_timestamp - utc_tick_start ).

2.7 Arithmetic

The OFFSET is defined just like the timestamp value, the difference is that the second in OFFSET can be negative.

Since OFFSET don't have timescale indicator in it, we can add or subtract a offset to one existing timestamp, or get a offset object from two timestamp.

2.8 Comparation

Differnet timestamp may belong to different timescale, so comparation must take timescale into consideration.

But with the function of converting timestamp into GPS timescale, this work becomes pretty easy, all we need to do is converting two timestamp into GPS timestamp, then compare them.

Comparation function will return 0 if t1=t2, 1 if t1>t2, and -1 if t1<t2.

-- ChenLi - 13 Sep 2013
Topic revision: r10 - 09 Feb 2014, HarlanStenn

This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Network Time Foundation Community Wiki? Send feedback