-mm generic clocksoure API

plain text document attachment (clocksource_init_call.patch) Since it's likely that this interface would get used during bootup I moved all the clocksource registration into the postcore initcall. This also eliminated some clocksource shuffling during bootup.

plain text document attachment (clocksource_cleanup.patch)

Signed-off-by Daniel Walker <[email protected]>

---
 include/linux/clocksource.h |    2 +-
 kernel/time/clocksource.c   |    6 +++---
 kernel/timer.c              |    7 ++++---
 3 files changed, 8 insertions(+), 7 deletions(-)

Index: linux-2.6.17/include/linux/clocksource.h
===================================================================

include/linux/clocksource.h +1 -1

@@ -159,7 +159,7 @@ static inline s64 cyc2ns(struct clocksou
  * Unless you're the timekeeping code, you should not be using this!
  */
 static inline void clocksource_calculate_interval(struct clocksource *c,
-						unsigned long length_nsec)
+					  	  unsigned long length_nsec)
 {
 	u64 tmp;
 

Index: linux-2.6.17/kernel/time/clocksource.c
===================================================================

kernel/time/clocksource.c +3 -3

@@ -143,7 +143,7 @@ int clocksource_register(struct clocksou
 	/* check if clocksource is already registered */
 	if (is_registered_source(c)) {
 		printk("register_clocksource: Cannot register %s. "
-			"Already registered!", c->name);
+		       "Already registered!", c->name);
 		ret = -EBUSY;
 	} else {
 		/* register it */

@@ -262,10 +262,10 @@ sysfs_show_available_clocksources(struct
  * Sysfs setup bits:
  */
 static SYSDEV_ATTR(current_clocksource, 0600, sysfs_show_current_clocksources,
-			sysfs_override_clocksource);
+		   sysfs_override_clocksource);
 
 static SYSDEV_ATTR(available_clocksource, 0600,
-			sysfs_show_available_clocksources, NULL);
+		   sysfs_show_available_clocksources, NULL);
 
 static struct sysdev_class clocksource_sysclass = {
 	set_kset_name("clocksource"),

Index: linux-2.6.17/kernel/timer.c
===================================================================

kernel/timer.c +4 -4

@@ -924,7 +924,7 @@ static int change_clocksource(void)
 		clock = new;
 		clock->cycle_last = now;
 		printk(KERN_INFO "Time: %s clocksource has been installed.\n",
-					clock->name);
+		       clock->name);
 		return 1;
 	} else if (clock->update_callback) {
 		return clock->update_callback();

@@ -932,7 +932,7 @@ static int change_clocksource(void)
 	return 0;
 }
 #else
-#define change_clocksource() (0)
+#define change_clocksource()	do { 0; } while(0)
 #endif
 
 /**

@@ -1149,7 +1149,8 @@ static void update_wall_time(void)
 
 		/* accumulate error between NTP and clock interval */
 		clock->error += current_tick_length();
-		clock->error -= clock->xtime_interval << (TICK_LENGTH_SHIFT - clock->shift);
+		clock->error -= clock->xtime_interval <<
+				(TICK_LENGTH_SHIFT - clock->shift);
 	}
 
 	/* correct the clock when NTP error is too big */
 
--

plain text document attachment (clocksource_user_api.patch) This introduces some new API calls,

- clocksource_get_clock()
Allows a clock lookup by name.
- clocksource_rating_change()
Used by a clocksource to signal a rating change. Replaces reselect_clocksource()

I also moved the the clock source list to a plist, which removes some lookup overhead in the average case.

Signed-off-by Daniel Walker <[email protected]>

---
 arch/i386/kernel/tsc.c      |    2 
 include/linux/clocksource.h |   45 ++++++++++++-
 kernel/time/clocksource.c   |  149 ++++++++++++++++++++++++++++----------------
 3 files changed, 139 insertions(+), 57 deletions(-)

Index: linux-2.6.17/arch/i386/kernel/tsc.c
===================================================================

arch/i386/kernel/tsc.c +1 -1

@@ -351,7 +351,7 @@ static int tsc_update_callback(void)
 	/* check to see if we should switch to the safe clocksource: */
 	if (clocksource_tsc.rating != 50 && check_tsc_unstable()) {
 		clocksource_tsc.rating = 50;
-		clocksource_reselect();
+		clocksource_rating_change(&clocksource_tsc);
 		change = 1;
 	}
 

Index: linux-2.6.17/include/linux/clocksource.h
===================================================================

include/linux/clocksource.h +41 -4

@@ -12,12 +12,20 @@
 #include <linux/timex.h>
 #include <linux/time.h>
 #include <linux/list.h>
+#include <linux/plist.h>
+#include <linux/sysdev.h>
 #include <asm/div64.h>
 #include <asm/io.h>
 
 /* clocksource cycle base type */
 typedef u64 cycle_t;
 
+/*
+ * This is the only generic clock, it should be used
+ * for early initialization.
+ */
+extern struct clocksource clocksource_jiffies;
+
 /**
  * struct clocksource - hardware abstraction for a free running counter
  *	Provides mostly state-free accessors to the underlying hardware.

@@ -51,7 +59,7 @@ typedef u64 cycle_t;
  */
 struct clocksource {
 	char *name;
-	struct list_head list;
+	struct plist_node list;
 	int rating;
 	cycle_t (*read)(void);
 	cycle_t mask;

@@ -148,6 +156,25 @@ static inline s64 cyc2ns(struct clocksou
 }
 
 /**
+ * ns2cyc - converts nanoseconds to clocksource cycles
+ * @cs:		Pointer to clocksource
+ * @ns:		Nanoseconds
+ *
+ * Uses the clocksource to convert nanoseconds back to cycles.
+ *
+ * XXX - This could use some mult_lxl_ll() asm optimization
+ */
+static inline cycle_t ns2cyc(struct clocksource *cs, s64 ns)
+{
+	u64 ret = ns;
+
+	ret <<= cs->shift;
+	do_div(ret, cs->mult);
+
+	return ret;
+}
+
+/**
  * clocksource_calculate_interval - Calculates a clocksource interval struct
  *
  * @c:		Pointer to clocksource.

@@ -178,8 +205,18 @@ static inline void clocksource_calculate
 
 
 /* used to install a new clocksource */
-int clocksource_register(struct clocksource*);
-void clocksource_reselect(void);
-struct clocksource* clocksource_get_next(void);
+extern int clocksource_register(struct clocksource*);
+extern void clocksource_rating_change(struct clocksource*);
+extern struct clocksource * clocksource_get_clock(char*);
 
+/**
+ * clocksource_get_best_clock - Finds highest rated clocksource
+ *
+ * Returns the highest rated clocksource. If none are register the
+ * jiffies clock is returned.
+ */
+static inline struct clocksource * clocksource_get_best_clock(void)
+{
+	return clocksource_get_clock(NULL);
+}
 #endif /* _LINUX_CLOCKSOURCE_H */

Index: linux-2.6.17/kernel/time/clocksource.c
===================================================================

kernel/time/clocksource.c +52 -37

 /*[Clocksource internal variables]---------
  * curr_clocksource:
  *	currently selected clocksource. Initialized to clocksource_jiffies.
  * next_clocksource:
  *	pending next selected clocksource.
  * clocksource_list:
- *	linked list with the registered clocksources
+ *	priority list with the registered clocksources
  * clocksource_lock:
  *	protects manipulations to curr_clocksource and next_clocksource
  *	and the clocksource_list

@@ -47,7 +52,8 @@ extern struct clocksource clocksource_ji
  */
 static struct clocksource *curr_clocksource = &clocksource_jiffies;
 static struct clocksource *next_clocksource;
-static LIST_HEAD(clocksource_list);
+static struct plist_head clocksource_list =
+	PLIST_HEAD_INIT(clocksource_list, clocksource_lock);
 static DEFINE_SPINLOCK(clocksource_lock);
 static char override_name[32];
 

@@ -70,84 +76,111 @@ struct clocksource *clocksource_get_next
 }
 
 /**
- * select_clocksource - Finds the best registered clocksource.
+ * __is_registered - Returns a clocksource if it's registered
+ * @name:		name of the clocksource to return
  *
  * Private function. Must hold clocksource_lock when called.
  *
- * Looks through the list of registered clocksources, returning
- * the one with the highest rating value. If there is a clocksource
- * name that matches the override string, it returns that clocksource.
+ * Returns the clocksource if registered, zero otherwise.
+ * If no clocksources are registered the jiffies clock is
+ * returned.
  */
-static struct clocksource *select_clocksource(void)
+static struct clocksource * __is_registered(char * name)
 {
-	struct clocksource *best = NULL;
-	struct list_head *tmp;
+	struct plist_node *tmp;
 
-	list_for_each(tmp, &clocksource_list) {
+	plist_for_each(tmp, &clocksource_list) {
 		struct clocksource *src;
 
 		src = list_entry(tmp, struct clocksource, list);
-		if (!best)
-			best = src;
-
-		/* check for override: */
-		if (strlen(src->name) == strlen(override_name) &&
-		    !strcmp(src->name, override_name)) {
-			best = src;
-			break;
-		}
-		/* pick the highest rating: */
-		if (src->rating > best->rating)
-		 	best = src;
+		if (!strcmp(src->name, name))
+			return src;
 	}
 
-	return best;
+	return 0;
 }
 
 /**
- * is_registered_source - Checks if clocksource is registered
- * @c:		pointer to a clocksource
+ * __get_clock - Finds a specific clocksource
+ * @name:		name of the clocksource to return
  *
- * Private helper function. Must hold clocksource_lock when called.
+ * Private function. Must hold clocksource_lock when called.
  *
- * Returns one if the clocksource is already registered, zero otherwise.
+ * Returns the clocksource if registered, zero otherwise.
+ * If the @name is null the highest rated clock is returned.
  */
-static int is_registered_source(struct clocksource *c)
+static inline struct clocksource * __get_clock(char * name)
 {
-	int len = strlen(c->name);
-	struct list_head *tmp;
 
-	list_for_each(tmp, &clocksource_list) {
-		struct clocksource *src;
+	if (unlikely(plist_head_empty(&clocksource_list)))
+		return &clocksource_jiffies;
 
-		src = list_entry(tmp, struct clocksource, list);
-		if (strlen(src->name) == len &&	!strcmp(src->name, c->name))
-			return 1;
-	}
+	if (!name)
+		return plist_first_entry(&clocksource_list, struct clocksource,
+					 list);
 
-	return 0;
+	return __is_registered(name);
+}
+
+/**
+ * clocksource_get_clock - Finds a specific clocksource
+ * @name:		name of the clocksource to return
+ *
+ * Returns the clocksource if registered, zero otherwise.
+ */
+struct clocksource * clocksource_get_clock(char * name)
+{
+	struct clocksource * ret;
+	unsigned long flags;
+
+	spin_lock_irqsave(&clocksource_lock, flags);
+	ret = __get_clock(name);
+	spin_unlock_irqrestore(&clocksource_lock, flags);
+	return ret;
+}
+
+
+/**
+ * select_clocksource - Finds the best registered clocksource.
+ *
+ * Private function. Must hold clocksource_lock when called.
+ *
+ * Looks through the list of registered clocksources, returning

kernel/time/clocksource.c +2 -1

 /**
  * clocksource_register - Used to install new clocksources
  * @t:		clocksource to be registered
  *
- * Returns -EBUSY if registration fails, zero otherwise.
+ * Returns -EBUSY clock is already registered,
+ * Returns -EINVAL if clocksource is invalid,

kernel/time/clocksource.c +23 -12

 	spin_lock_irqsave(&clocksource_lock, flags);
-	/* check if clocksource is already registered */
-	if (is_registered_source(c)) {
-		printk("register_clocksource: Cannot register %s. "
+	if (unlikely(!plist_node_empty(&c->list) && __is_registered(c->name))) {
+		printk("register_clocksource: Cannot register %s clocksource. "
 		       "Already registered!", c->name);
 		ret = -EBUSY;
 	} else {
-		/* register it */
- 		list_add(&c->list, &clocksource_list);
+		plist_node_init(&c->list, CLOCKSOURCE_RATING(c->rating));
+ 		plist_add(&c->list, &clocksource_list);
 		/* scan the registered clocksources, and pick the best one */
 		next_clocksource = select_clocksource();
 	}

@@ -157,21 +190,32 @@ int clocksource_register(struct clocksou
 EXPORT_SYMBOL(clocksource_register);
 
 /**
- * clocksource_reselect - Rescan list for next clocksource
+ * clocksource_rating_change - Allows dynamic rating changes for register
+ *                           clocksources.
  *
- * A quick helper function to be used if a clocksource changes its
- * rating. Forces the clocksource list to be re-scanned for the best
- * clocksource.
+ * Signals that a clocksource is dynamically changing it's rating.
+ * This could happen if a clocksource becomes more/less stable.
  */
-void clocksource_reselect(void)
+void clocksource_rating_change(struct clocksource *c)
 {
 	unsigned long flags;
 
+	if (unlikely(plist_node_empty(&c->list)))
+		return;
+
 	spin_lock_irqsave(&clocksource_lock, flags);
+
+	/*
+	 * Re-register the clocksource with it's new rating.
+	 */
+	plist_del(&c->list, &clocksource_list);
+	plist_node_init(&c->list, CLOCKSOURCE_RATING(c->rating));
+	plist_add(&c->list, &clocksource_list);
+
 	next_clocksource = select_clocksource();
 	spin_unlock_irqrestore(&clocksource_lock, flags);
 }
-EXPORT_SYMBOL(clocksource_reselect);
+EXPORT_SYMBOL(clocksource_rating_change);
 
 /**
  * sysfs_show_current_clocksources - sysfs interface for current clocksource

@@ -236,16 +280,17 @@ static ssize_t sysfs_override_clocksourc
  * @dev:	unused
  * @buf:	char buffer to be filled with clocksource list
  *
- * Provides sysfs interface for listing registered clocksources
+ * Provides sysfs interface for listing registered clocksources.
+ * Output in priority sorted order.
  */
 static ssize_t
 sysfs_show_available_clocksources(struct sys_device *dev, char *buf)
 {

kernel/time/clocksource.c line 38

Quoted 5 lines

kernel/time/clocksource.c +4 -0

+/*
+ * Internally used to invert the rating, so lower is better.
+ */
+#define CLOCKSOURCE_RATING(x)	(INT_MAX-x)

Since this is used for the plist bits, could it get a more explicit name?

kernel/time/clocksource.c struct clocksource *clocksource_get_next · line 175

Quoted 8 lines

int clocksource_register(struct clocksource *c)
{

kernel/time/clocksource.c +3 -0

 	int ret = 0;
 	unsigned long flags;
 
+	if (unlikely(!c))
+		return -EINVAL;
+

I'm not sure I understand the need for this. Is it really likely someone would pass NULL to clocksource_register()?

Quoted 11 lines

kernel/time/clocksource.c struct clocksource *clocksource_get_next · line 175

Quoted 8 lines

int clocksource_register(struct clocksource *c)
{

kernel/time/clocksource.c +3 -0

 	int ret = 0;
 	unsigned long flags;
 
+	if (unlikely(!c))
+		return -EINVAL;
+

I'm not sure I understand the need for this. Is it really likely someone would pass NULL to clocksource_register()?

Not likely, I was just covering all possibilities.. It might be better as a BUG_ON() actually.

plain text document attachment (clocksource_remove_update_callback.patch) With the new notifier block the update_callback becomes obsolete.

Signed-off-by Daniel Walker <[email protected]>

---
 arch/i386/kernel/tsc.c      |    5 +++--
 include/linux/clocksource.h |    2 --
 2 files changed, 3 insertions(+), 4 deletions(-)

Index: linux-2.6.17/arch/i386/kernel/tsc.c
===================================================================

arch/i386/kernel/tsc.c +0 -0

@@ -60,9 +60,12 @@ static inline int check_tsc_unstable(voi
 	return tsc_unstable;

arch/i386/kernel/tsc.c +0 -2

@@ -322,7 +325,6 @@ core_initcall(cpufreq_tsc);
 /* clock source code */
 
 static unsigned long current_tsc_khz = 0;
-static int tsc_update_callback(void);
 
 static cycle_t read_tsc(void)
 {

@@ -340,7 +342,6 @@ static struct clocksource clocksource_ts
 	.mask			= CLOCKSOURCE_MASK(64),
 	.mult			= 0, /* to be set */
 	.shift			= 22,
-	.update_callback	= tsc_update_callback,
 	.is_continuous		= 1,
 };
 

Index: linux-2.6.17/include/linux/clocksource.h
===================================================================

include/linux/clocksource.h +0 -1

@@ -60,7 +60,6 @@ extern struct clocksource clocksource_ji
  *			subtraction of non 64 bit counters
  * @mult:		cycle to nanosecond multiplier
  * @shift:		cycle to nanosecond divisor (power of two)
- * @update_callback:	called when safe to alter clocksource values
  * @is_continuous:	defines if clocksource is free-running.
  * @cycle_interval:	Used internally by timekeeping core, please ignore.
  * @xtime_interval:	Used internally by timekeeping core, please ignore.

plain text document attachment (clocksource_api_cleanup_on_mm.patch) Some additional clean up only on the -mm tree. Moves the adjust functions into kernel/time/clocksource.c .

These functions directly modify the clocksource multiplier based on ntp error. These adjustments will effect other users of that clock. This hasn't been addressed in my patch set, since it needs some discussion.

Hmmmm. Yea, some additional discussion here would probably be needed

At the moment, I'd prefer to keep the clocksource_adjust bits with the timekeeping code, however I'd also prefer to remove the timekeeping specific fields (cycle_last, cycle_interval, xtime_nsec, xtime_interval, error) from the clocksource structure and instead keep them in a timekeeping specific structure (which may also point to a clocksource).

This would keep a clean separation between the clocksource's abstraction that keeps as little state as possible and the timekeeping code's internal state. However the point you bring up above is an interesting
issue: Do all users of the generic clocksource structure want the clocksource to be NTP adjusted?

If we allow for non-ntp adjusted access to the clocksources, we may have consistency issues between users comparing say sched_clock() and clock_gettime() intervals. Further, if those users do want NTP adjusted counters, why aren't they just using the timekeeping subsystem?

This does put some question as to what exactly would be the uses of the clocksource structure outside of the timekeeping realm. Sure, sched_clock() is a reasonable example, although since sched_clock has such specific latency needs (we probably shouldn't go touching off-chip hardware on every sched_clock call) and can be careful to avoid TSC skew unlike the timekeeping code, its selection algorithm is going to be very arch specific. So I'm not sure its really an ideal use of the clocksource interface (as its not too difficult to just keep sched_clock arch specific).

I do feel making the abstraction clean and generic is a good thing just for code readability (and I very much appreciate your work here!), but I'm not really sure that the need for clocksource access outside the timekeeping subsystem has been well expressed. Do you have some other examples other then sched_clock that might show further uses for this abstraction?

Quoted 9 lines · john stultz

Hmmmm. Yea, some additional discussion here would probably be needed

At the moment, I'd prefer to keep the clocksource_adjust bits with the timekeeping code, however I'd also prefer to remove the timekeeping specific fields (cycle_last, cycle_interval, xtime_nsec, xtime_interval, error) from the clocksource structure and instead keep them in a timekeeping specific structure (which may also point to a clocksource).

Quoted 5 lines

This would keep a clean separation between the clocksource's abstraction that keeps as little state as possible and the timekeeping code's internal state. However the point you bring up above is an interesting
issue: Do all users of the generic clocksource structure want the clocksource to be NTP adjusted?

Since the output from the clocksource is a lowlevel timestamp I don't think the users of it would want it to be ntp adjusted. It would also be a little odd, since the ntp adjustment would be attached only to a single clock.

Quoted 4 lines

If we allow for non-ntp adjusted access to the clocksources, we may have consistency issues between users comparing say sched_clock() and clock_gettime() intervals. Further, if those users do want NTP adjusted counters, why aren't they just using the timekeeping subsystem?

I imagine the users of the interface would be compartmentalized. Taking sched_clock as an example the output is only compared to itself and not to output from other interfaces.

Quoted 9 lines

This does put some question as to what exactly would be the uses of the clocksource structure outside of the timekeeping realm. Sure, sched_clock() is a reasonable example, although since sched_clock has such specific latency needs (we probably shouldn't go touching off-chip hardware on every sched_clock call) and can be careful to avoid TSC skew unlike the timekeeping code, its selection algorithm is going to be very arch specific. So I'm not sure its really an ideal use of the clocksource interface (as its not too difficult to just keep sched_clock arch specific).

Part of the reason to have a generic sched_clock() (and the generic clocksource interface in general) is to eliminate the inefficienty of duplicating shift and mult functionality in each arch (and on ARM it's per board).

So if you correctly implement a clocksource structure for
your hardware you will at least expose a usable sched_clock() and generic timeofday. Then if we add more users of the interface then more functionality is exposed.

Another instances of this is when instrumentation is needing a of fast low level timestamp. In the past to accomplish this one would need a per arch change to read a clock, then potentially duplicate a shift and mult type computation in order to covert to nanosecond. One good example of this is latency tracing in the -rt tree. I can imagine some good and valid instrumentation having a long road of acceptable because the time stamping portion would need to flow through several different arch and potentially board maintainers.

I've also imagined that some usage of jiffies could be converted to use this interface if it was appropriate. Since jiffies is hooked to the tick, and the tick is getting more and more irregular, a clocksource might be a relatively good replacement.

Quoted 6 lines

I do feel making the abstraction clean and generic is a good thing just for code readability (and I very much appreciate your work here!), but I'm not really sure that the need for clocksource access outside the timekeeping subsystem has been well expressed. Do you have some other examples other then sched_clock that might show further uses for this abstraction?

I've converted latency tracing to an earlier version of the API , but I don't have any other examples prepared. I think it's important to get the API settled before I start converting anything else.

Quoted 3 lines

I imagine the users of the interface would be compartmentalized. Taking sched_clock as an example the output is only compared to itself and not to output from other interfaces.

Agreed on both points. Although I suspect this point will need to be made explicit.

Quoted 4 lines

So if you correctly implement a clocksource structure for
your hardware you will at least expose a usable sched_clock() and generic timeofday. Then if we add more users of the interface then more functionality is exposed.

Well, this point might need some work. sched_clock has quite a different correctness/performance tradeoff when compared against timeofday. If one correctly implements a clocksource for something like the ACPI PM, I doubt they'd want to use it for sched_clock (due to its ~1us access latency). Additionally, since sched_clock doesn't require (for its original purpose, at least) the TSC synchronization that is essential for timekeeping, how will sched_clock determine which clocksource to use on a system were the TSC is unsyched and marked bad?

Quoted 8 lines

Another instances of this is when instrumentation is needing a of fast low level timestamp. In the past to accomplish this one would need a per arch change to read a clock, then potentially duplicate a shift and mult type computation in order to covert to nanosecond. One good example of this is latency tracing in the -rt tree. I can imagine some good and valid instrumentation having a long road of acceptable because the time stamping portion would need to flow through several different arch and potentially board maintainers.

This sounds reasonable, but also I'd question if sched_clock or get_cycles would be appropriate here. Further, if the mult/shift cost is acceptable, why not just use the timeofday as the cost will be similar.

Quoted 4 lines

I've also imagined that some usage of jiffies could be converted to use this interface if it was appropriate. Since jiffies is hooked to the tick, and the tick is getting more and more irregular, a clocksource might be a relatively good replacement.

Hmmm. That'd be a harder sell for me. Probably would want those users to move to the timeofday, or alternatively, drive jiffies off of the timekeeping code rather then the interrupt handler to ensure it stays synced (something I'm plotting once the timekeeping code settles down).

Quoted 10 lines

Quoted 6 lines

I do feel making the abstraction clean and generic is a good thing just for code readability (and I very much appreciate your work here!), but I'm not really sure that the need for clocksource access outside the timekeeping subsystem has been well expressed. Do you have some other examples other then sched_clock that might show further uses for this abstraction?

I've converted latency tracing to an earlier version of the API , but I don't have any other examples prepared. I think it's important to get the API settled before I start converting anything else.

Again, I think your patch set looks good for the most part (its just the last few bits I worry about). I'm very much interested to see where you go with this, as I feel sched_clock (on i386 atleast) needs some love and attention and I'm excited to see new uses for the clocksource abstraction. However, I do want to make sure that we think the use cases out to avoid over-engineering the wrong bits.