aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/linux/timecompare.h125
-rw-r--r--kernel/time/Makefile2
-rw-r--r--kernel/time/timecompare.c193
3 files changed, 1 insertions, 319 deletions
diff --git a/include/linux/timecompare.h b/include/linux/timecompare.h
deleted file mode 100644
index 546e2234e4b3..000000000000
--- a/include/linux/timecompare.h
+++ /dev/null
@@ -1,125 +0,0 @@
1/*
2 * Utility code which helps transforming between two different time
3 * bases, called "source" and "target" time in this code.
4 *
5 * Source time has to be provided via the timecounter API while target
6 * time is accessed via a function callback whose prototype
7 * intentionally matches ktime_get() and ktime_get_real(). These
8 * interfaces where chosen like this so that the code serves its
9 * initial purpose without additional glue code.
10 *
11 * This purpose is synchronizing a hardware clock in a NIC with system
12 * time, in order to implement the Precision Time Protocol (PTP,
13 * IEEE1588) with more accurate hardware assisted time stamping. In
14 * that context only synchronization against system time (=
15 * ktime_get_real()) is currently needed. But this utility code might
16 * become useful in other situations, which is why it was written as
17 * general purpose utility code.
18 *
19 * The source timecounter is assumed to return monotonically
20 * increasing time (but this code does its best to compensate if that
21 * is not the case) whereas target time may jump.
22 *
23 * The target time corresponding to a source time is determined by
24 * reading target time, reading source time, reading target time
25 * again, then assuming that average target time corresponds to source
26 * time. In other words, the assumption is that reading the source
27 * time is slow and involves equal time for sending the request and
28 * receiving the reply, whereas reading target time is assumed to be
29 * fast.
30 *
31 * Copyright (C) 2009 Intel Corporation.
32 * Author: Patrick Ohly <patrick.ohly@intel.com>
33 *
34 * This program is free software; you can redistribute it and/or modify it
35 * under the terms and conditions of the GNU General Public License,
36 * version 2, as published by the Free Software Foundation.
37 *
38 * This program is distributed in the hope it will be useful, but WITHOUT
39 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
40 * FITNESS FOR A PARTICULAR PURPOSE. * See the GNU General Public License for
41 * more details.
42 *
43 * You should have received a copy of the GNU General Public License along with
44 * this program; if not, write to the Free Software Foundation, Inc.,
45 * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
46 */
47#ifndef _LINUX_TIMECOMPARE_H
48#define _LINUX_TIMECOMPARE_H
49
50#include <linux/clocksource.h>
51#include <linux/ktime.h>
52
53/**
54 * struct timecompare - stores state and configuration for the two clocks
55 *
56 * Initialize to zero, then set source/target/num_samples.
57 *
58 * Transformation between source time and target time is done with:
59 * target_time = source_time + offset +
60 * (source_time - last_update) * skew /
61 * TIMECOMPARE_SKEW_RESOLUTION
62 *
63 * @source: used to get source time stamps via timecounter_read()
64 * @target: function returning target time (for example, ktime_get
65 * for monotonic time, or ktime_get_real for wall clock)
66 * @num_samples: number of times that source time and target time are to
67 * be compared when determining their offset
68 * @offset: (target time - source time) at the time of the last update
69 * @skew: average (target time - source time) / delta source time *
70 * TIMECOMPARE_SKEW_RESOLUTION
71 * @last_update: last source time stamp when time offset was measured
72 */
73struct timecompare {
74 struct timecounter *source;
75 ktime_t (*target)(void);
76 int num_samples;
77
78 s64 offset;
79 s64 skew;
80 u64 last_update;
81};
82
83/**
84 * timecompare_transform - transform source time stamp into target time base
85 * @sync: context for time sync
86 * @source_tstamp: the result of timecounter_read() or
87 * timecounter_cyc2time()
88 */
89extern ktime_t timecompare_transform(struct timecompare *sync,
90 u64 source_tstamp);
91
92/**
93 * timecompare_offset - measure current (target time - source time) offset
94 * @sync: context for time sync
95 * @offset: average offset during sample period returned here
96 * @source_tstamp: average source time during sample period returned here
97 *
98 * Returns number of samples used. Might be zero (= no result) in the
99 * unlikely case that target time was monotonically decreasing for all
100 * samples (= broken).
101 */
102extern int timecompare_offset(struct timecompare *sync,
103 s64 *offset,
104 u64 *source_tstamp);
105
106extern void __timecompare_update(struct timecompare *sync,
107 u64 source_tstamp);
108
109/**
110 * timecompare_update - update offset and skew by measuring current offset
111 * @sync: context for time sync
112 * @source_tstamp: the result of timecounter_read() or
113 * timecounter_cyc2time(), pass zero to force update
114 *
115 * Updates are only done at most once per second.
116 */
117static inline void timecompare_update(struct timecompare *sync,
118 u64 source_tstamp)
119{
120 if (!source_tstamp ||
121 (s64)(source_tstamp - sync->last_update) >= NSEC_PER_SEC)
122 __timecompare_update(sync, source_tstamp);
123}
124
125#endif /* _LINUX_TIMECOMPARE_H */
diff --git a/kernel/time/Makefile b/kernel/time/Makefile
index e2fd74b8e8c2..ff7d9d2ab504 100644
--- a/kernel/time/Makefile
+++ b/kernel/time/Makefile
@@ -1,4 +1,4 @@
1obj-y += timekeeping.o ntp.o clocksource.o jiffies.o timer_list.o timecompare.o 1obj-y += timekeeping.o ntp.o clocksource.o jiffies.o timer_list.o
2obj-y += timeconv.o posix-clock.o alarmtimer.o 2obj-y += timeconv.o posix-clock.o alarmtimer.o
3 3
4obj-$(CONFIG_GENERIC_CLOCKEVENTS_BUILD) += clockevents.o 4obj-$(CONFIG_GENERIC_CLOCKEVENTS_BUILD) += clockevents.o
diff --git a/kernel/time/timecompare.c b/kernel/time/timecompare.c
deleted file mode 100644
index a9ae369925ce..000000000000
--- a/kernel/time/timecompare.c
+++ /dev/null
@@ -1,193 +0,0 @@
1/*
2 * Copyright (C) 2009 Intel Corporation.
3 * Author: Patrick Ohly <patrick.ohly@intel.com>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19
20#include <linux/timecompare.h>
21#include <linux/module.h>
22#include <linux/slab.h>
23#include <linux/math64.h>
24#include <linux/kernel.h>
25
26/*
27 * fixed point arithmetic scale factor for skew
28 *
29 * Usually one would measure skew in ppb (parts per billion, 1e9), but
30 * using a factor of 2 simplifies the math.
31 */
32#define TIMECOMPARE_SKEW_RESOLUTION (((s64)1)<<30)
33
34ktime_t timecompare_transform(struct timecompare *sync,
35 u64 source_tstamp)
36{
37 u64 nsec;
38
39 nsec = source_tstamp + sync->offset;
40 nsec += (s64)(source_tstamp - sync->last_update) * sync->skew /
41 TIMECOMPARE_SKEW_RESOLUTION;
42
43 return ns_to_ktime(nsec);
44}
45EXPORT_SYMBOL_GPL(timecompare_transform);
46
47int timecompare_offset(struct timecompare *sync,
48 s64 *offset,
49 u64 *source_tstamp)
50{
51 u64 start_source = 0, end_source = 0;
52 struct {
53 s64 offset;
54 s64 duration_target;
55 } buffer[10], sample, *samples;
56 int counter = 0, i;
57 int used;
58 int index;
59 int num_samples = sync->num_samples;
60
61 if (num_samples > ARRAY_SIZE(buffer)) {
62 samples = kmalloc(sizeof(*samples) * num_samples, GFP_ATOMIC);
63 if (!samples) {
64 samples = buffer;
65 num_samples = ARRAY_SIZE(buffer);
66 }
67 } else {
68 samples = buffer;
69 }
70
71 /* run until we have enough valid samples, but do not try forever */
72 i = 0;
73 counter = 0;
74 while (1) {
75 u64 ts;
76 ktime_t start, end;
77
78 start = sync->target();
79 ts = timecounter_read(sync->source);
80 end = sync->target();
81
82 if (!i)
83 start_source = ts;
84
85 /* ignore negative durations */
86 sample.duration_target = ktime_to_ns(ktime_sub(end, start));
87 if (sample.duration_target >= 0) {
88 /*
89 * assume symetric delay to and from source:
90 * average target time corresponds to measured
91 * source time
92 */
93 sample.offset =
94 (ktime_to_ns(end) + ktime_to_ns(start)) / 2 -
95 ts;
96
97 /* simple insertion sort based on duration */
98 index = counter - 1;
99 while (index >= 0) {
100 if (samples[index].duration_target <
101 sample.duration_target)
102 break;
103 samples[index + 1] = samples[index];
104 index--;
105 }
106 samples[index + 1] = sample;
107 counter++;
108 }
109
110 i++;
111 if (counter >= num_samples || i >= 100000) {
112 end_source = ts;
113 break;
114 }
115 }
116
117 *source_tstamp = (end_source + start_source) / 2;
118
119 /* remove outliers by only using 75% of the samples */
120 used = counter * 3 / 4;
121 if (!used)
122 used = counter;
123 if (used) {
124 /* calculate average */
125 s64 off = 0;
126 for (index = 0; index < used; index++)
127 off += samples[index].offset;
128 *offset = div_s64(off, used);
129 }
130
131 if (samples && samples != buffer)
132 kfree(samples);
133
134 return used;
135}
136EXPORT_SYMBOL_GPL(timecompare_offset);
137
138void __timecompare_update(struct timecompare *sync,
139 u64 source_tstamp)
140{
141 s64 offset;
142 u64 average_time;
143
144 if (!timecompare_offset(sync, &offset, &average_time))
145 return;
146
147 if (!sync->last_update) {
148 sync->last_update = average_time;
149 sync->offset = offset;
150 sync->skew = 0;
151 } else {
152 s64 delta_nsec = average_time - sync->last_update;
153
154 /* avoid division by negative or small deltas */
155 if (delta_nsec >= 10000) {
156 s64 delta_offset_nsec = offset - sync->offset;
157 s64 skew; /* delta_offset_nsec *
158 TIMECOMPARE_SKEW_RESOLUTION /
159 delta_nsec */
160 u64 divisor;
161
162 /* div_s64() is limited to 32 bit divisor */
163 skew = delta_offset_nsec * TIMECOMPARE_SKEW_RESOLUTION;
164 divisor = delta_nsec;
165 while (unlikely(divisor >= ((s64)1) << 32)) {
166 /* divide both by 2; beware, right shift
167 of negative value has undefined
168 behavior and can only be used for
169 the positive divisor */
170 skew = div_s64(skew, 2);
171 divisor >>= 1;
172 }
173 skew = div_s64(skew, divisor);
174
175 /*
176 * Calculate new overall skew as 4/16 the
177 * old value and 12/16 the new one. This is
178 * a rather arbitrary tradeoff between
179 * only using the latest measurement (0/16 and
180 * 16/16) and even more weight on past measurements.
181 */
182#define TIMECOMPARE_NEW_SKEW_PER_16 12
183 sync->skew =
184 div_s64((16 - TIMECOMPARE_NEW_SKEW_PER_16) *
185 sync->skew +
186 TIMECOMPARE_NEW_SKEW_PER_16 * skew,
187 16);
188 sync->last_update = average_time;
189 sync->offset = offset;
190 }
191 }
192}
193EXPORT_SYMBOL_GPL(__timecompare_update);
generated by cgit v1.2.2 (git 2.25.0) at 2025-03-31 14:36:53 -0400