lock stat for 2.6.19-rt1
cover lock stat for 2.6.19-rt1
Hello,
I'm please to announce the "lock stat" patch which instruments all locks in the kernel tracking contention against the slow path of an a rt_mutex in -rt kernels before blocking and possibly priority inheritence boosting. This is for 2.6.19-rt1. In the real time patch, all locks such as a mutex, semaphore, etc... are funneled through the rt_mutex as well as locks such as a spinlock which preserve the semantics of BKL when hitting scheduler code.
On a contention, it increments a field atomically that's pointed in a variable within the rt_mutex structure. It records the numbers of times the rt_mutex is contented against during the lifetime of that lock.
By using a hash constructed out of __FILE__, __func__ and __LINE__ of the actual lock initializer function (spin_lock_init() and friends) single backing object within a red black tree based dictionary can serve to record these statistics versus explicitly tracking the life and death of a lock explicitly. This is more meaningful than having these statistics recorded on an individual lock instance. It's a higher order of expression with how lock statistics are represented since it's about the macro behavior of the kernel and therefore is more meaningful.
I'll defer the other parts of the discussion to the comments in the patch itself. I just want to get this patch right now with further delaying this.
It's quite similar to how lockdep also hooks into the kernel but I wasn't aware of how lockdep worked when I was writing this code only to be told by Peter Zijlstra after his review of the patch.
This is superior to lock meter for a number of reasons. First it's the -rt kernel (and we all know how I love the -rt kernel :) ) it is Linux specific, it hooks into lockdep closely and has a friendly proc interface to go with it with the ability to reset stats during load testing runs by simply writing to the file, /proc/lock_stat/contention.
Sample output is attached:
-------------------------------
[1, 1, 0] {finish_wait, -, 0}
[1, 1, 0] {lru_add_drain, -, 0}
[1, 1, 0] {rt_down_read, -, 0}
[1, 1, 0] {__sync_inodes, -, 0}
[1, 1, 0] {unix_create1, -, 0}
[1110, 1, 0] {kmem_cache_free, -, 0}
[11, 1, 0] {pdflush, -, 0}
[1, 123148, 0] {init_buffer_head, fs/buffer.c, 2968}
[1, 2, 0] {__svc_create, net/sunrpc/svc.c, 328}
[14, 11446, 0] {sock_lock_init, net/core/sock.c, 809}
[14373, 1, 0] {ide_intr, -, 0}
[14878, 13, 0] {create_workqueue_thread, kernel/workqueue.c, 347}
[15, 123148, 0] {init_buffer_head, fs/buffer.c, 2969}
[153, 1, 0] {__free_pages_ok, -, 0}
[17, 1, 0] {init_timers_cpu, kernel/timer.c, 1834}
[17533, 1, 0] {_atomic_dec_and_spin_lock, -, 0}
[203, 1, 0] {release_pages, -, 0}
[2040, 1, 0] {do_wait, -, 0}
[2, 1, 0] {cache_alloc_refill, -, 0}
[2, 1, 0] {sys_setsid, -, 0}
[23, 996648, 0] {inode_init_once, fs/inode.c, 199}
[242, 996648, 0] {inode_init_once, fs/inode.c, 197}
[251, 1, 0] {get_zone_pcp, -, 0}
[25, 1248, 0] {anon_vma_ctor, mm/rmap.c, 168}
[2725, 1, 0] {lock_kernel, -, 0}
[3, 1, 0] {lock_timer_base, -, 0}
[3, 1, 0] {serio_thread, -, 0}
[31, 81, 0] {kmem_list3_init, mm/slab.c, 411}
[32, 1, 0] {lru_cache_add_active, -, 0}
[3, 256, 0] {init, kernel/futex.c, 2776}
[33, 1, 0] {get_page_from_freelist, -, 0}
[35, 1, 0] {do_lookup, -, 0}
[37, 1, 0] {file_kill, -, 0}
[39, 1, 0] {__cache_free, -, 0}
[403, 204, 0] {sighand_ctor, kernel/fork.c, 1469}
[4, 16, 0] {xprt_create_transport, net/sunrpc/xprt.c, 930}
[4, 29369, 0] {mm_init, kernel/fork.c, 368}
[49, 2, 0] {journal_init_common, fs/jbd/journal.c, 666}
[5, 1, 0] {mm_init, -, 0}
[52, 1, 0] {lookup_mnt, -, 0}
[549, 0, 1349567] {, d_alloc_string, 1}
[5871, 2, 0] {journal_init_common, fs/jbd/journal.c, 667}
[59, 1, 0] {nv_probe, drivers/net/forcedeth.c, 4241}
[6, 11443, 0] {sock_init_data, net/core/sock.c, 1503}
[8, 2, 0] {journal_init_revoke, fs/jbd/revoke.c, 261}
[8264, 996648, 0] {inode_init_once, fs/inode.c, 196}
[8552, 996648, 0] {inode_init_once, fs/inode.c, 193}
[86, 1, 0] {exit_mmap, -, 0}
[86, 86258, 0] {init_waitqueue_head, kernel/wait.c, 15}
[8968, 1, 0] {iget_locked, -, 0}
[9, 1, 0] {tty_ldisc_try, -, 0}
[9, 1, 0] {uart_set_options, drivers/serial/serial_core.c, 1876}
@contention events = 86925
@found = 9
-------------------------------
The first column is the number of the times that object was contented against. The second is the number of times this lock object was initialized. The third is the annotation scheme that directly attaches the lock object (spinlock, etc..) in line with the function initializer to avoid the binary tree lookup.
This shows contention issue with inode access around what looks like a lock around a tree structure (inode_init_once @ lines 193/196) as well as lower layers of the IO system around the anticipatory scheduler and interrupt handlers. Keep in mind this is -rt so we're using interrupt threads here.
This result is a combination of series of normal "find" loads as a result of the machine being idle overnight in a 2x AMD process set up. I'm sure that bigger machines should generate more interesting loads from the IBM folks and others.
Thanks to all of the folks on #offtopic2 (Zwane Mwaikambo, nikita, Rik van Riel, the ever increasingly bitter Con Kolivas, Bill Irwin, etc...) for talking me through early stages of this process and general support.
I'm requesting review, comments and inclusion of this into the -rt series of patches as well as general help.
I've CCed folks that might be interested in this patch outside of the normal core -rt that I thought might find this interesting or have been friendly with me about -rt in the past.
bill
============================================================
linux/lock_stat.h +144 -0
@@ -0,0 +1,144 @@ +/* +* By Bill Huey (hui) at <[email protected]> +* +* Release under the what ever the Linux kernel chooses for a +* license, GNU Public License GPL v2 +* +* Tue Sep 5 17:27:48 PDT 2006 +* Created lock_stat.h +* +* Wed Sep 6 15:36:14 PDT 2006 +* Thinking about the object lifetime of a spinlock. Please refer to +* comments in kernel/lock_stat.c instead. +* +*/ + +#ifndef LOCK_STAT_H +#define LOCK_STAT_H + +#ifdef CONFIG_LOCK_STAT + +#include <linux/list.h> +#include <linux/rbtree.h> +#include <linux/kallsyms.h> +#include <linux/string.h> + +#include <asm/atomic.h> + +typedef struct lock_stat { +char function[KSYM_NAME_LEN ]; +int line; +char *file; + +atomic_t ncontended; +unsigned int ntracked; +atomic_t ninlined; + +struct rb_node rb_node; +struct list_head list_head; +}lock_stat_t ; + +typedef lock_stat_t *lock_stat_ref_t ; + +#define LOCK_STAT_INIT (field) +#define LOCK_STAT_INITIALIZER (field) { \ + __FILE__, __FUNCTION__, __LINE__, \ + ATOMIC_INIT(0), LIST_HEAD_INIT(field)} + +#define LOCK_STAT_NOTE __FILE__, __FUNCTION__, __LINE__ +#define LOCK_STAT_NOTE_VARS _file, _function, _line +#define LOCK_STAT_NOTE_PARAM_DECL const char *_file, \ + const char *_function, \ + int _line + +#define __COMMA_LOCK_STAT_FN_DECL , const char *_function +#define __COMMA_LOCK_STAT_FN_VAR , _function +#define __COMMA_LOCK_STAT_NOTE_FN , __FUNCTION__ + +#define __COMMA_LOCK_STAT_NOTE , LOCK_STAT_NOTE +#define __COMMA_LOCK_STAT_NOTE_VARS , LOCK_STAT_NOTE_VARS +#define __COMMA_LOCK_STAT_NOTE_PARAM_DECL , LOCK_STAT_NOTE_PARAM_DECL + + +#define __COMMA_LOCK_STAT_NOTE_FLLN_DECL , const char *_file, int _line +#define __COMMA_LOCK_STAT_NOTE_FLLN , __FILE__, __LINE__ +#define __COMMA_LOCK_STAT_NOTE_FLLN_VARS , _file, _line + +#define __COMMA_LOCK_STAT_INITIALIZER , .lock_stat = NULL, + +#define __COMMA_LOCK_STAT_IP_DECL , unsigned long _ip +#define __COMMA_LOCK_STAT_IP , _ip +#define __COMMA_LOCK_STAT_RET_IP , (unsigned long) __builtin_return_address(0) + +extern void lock_stat_init (struct lock_stat *ls); +extern void lock_stat_sys_init (void ); + +#define lock_stat_is_initialized (o) ((unsigned long) (*o)->file) + +extern void lock_stat_note_contention (lock_stat_ref_t *ls,unsigned long ip); +extern void lock_stat_print (void ); +extern void lock_stat_scoped_attach (lock_stat_ref_t *_s,LOCK_STAT_NOTE_PARAM_DECL ); + +#define ksym_strcmp (a, b) strncmp(a, b, KSYM_NAME_LEN) +#define ksym_strcpy (a, b) strncpy(a, b, KSYM_NAME_LEN) +#define ksym_strlen (a) strnlen(a, KSYM_NAME_LEN) + +/* +static inline char * ksym_strdup(const char *a) +{ +char *s = (char *) kmalloc(ksym_strlen(a), GFP_KERNEL); +return strncpy(s, a, KSYM_NAME_LEN); +} +*/ + +#define LS_INIT(name, h) { \ + /*.function,*/ .file = h, .line = 1, \ + .ntracked = 0, .ncontended = ATOMIC_INIT(0), \ + .list_head = LIST_HEAD_INIT(name.list_head), \ + .rb_node.rb_left = NULL, .rb_node.rb_left = NULL \ + } + +#define DECLARE_LS_ENTRY (name) \ + extern struct lock_stat _lock_stat_##name##_entry + +/* char _##name##_string[] = #name; \ +*/ + +#define DEFINE_LS_ENTRY (name) \ + struct lock_stat _lock_stat_##name##_entry = LS_INIT(_lock_stat_##name##_entry, #name "_string") + +DECLARE_LS_ENTRY (d_alloc); +DECLARE_LS_ENTRY (eventpoll_init_file); +/* +DECLARE_LS_ENTRY(get_empty_filp); +DECLARE_LS_ENTRY(init_once_1); +DECLARE_LS_ENTRY(init_once_2); +DECLARE_LS_ENTRY(inode_init_once_1); +DECLARE_LS_ENTRY(inode_init_once_2); +DECLARE_LS_ENTRY(inode_init_once_3); +DECLARE_LS_ENTRY(inode_init_once_4); +DECLARE_LS_ENTRY(inode_init_once_5); +DECLARE_LS_ENTRY(inode_init_once_6); +DECLARE_LS_ENTRY(inode_init_once_7); +*/ + +#else /* CONFIG_LOCK_STAT */ + +#define __COMMA_LOCK_STAT_FN_DECL +#define __COMMA_LOCK_STAT_FN_VAR +#define __COMMA_LOCK_STAT_NOTE_FN + +#define __COMMA_LOCK_STAT_NOTE_FLLN_DECL +#define __COMMA_LOCK_STAT_NOTE_FLLN +#define __COMMA_LOCK_STAT_NOTE_FLLN_VARS + +#define __COMMA_LOCK_STAT_INITIALIZER + +#define __COMMA_LOCK_STAT_IP_DECL +#define __COMMA_LOCK_STAT_IP +#define __COMMA_LOCK_STAT_RET_IP + +#endif /* CONFIG_LOCK_STAT */ + +#endif /* LOCK_STAT_H */ +
============================================================
lock_stat.c +668 -0
668 lines not on this page · raw message
Quoted 2 lines · Bill Huey
[8264, 996648, 0] {
inode_init_once,fs/inode.c, 196}
[8552, 996648, 0] {inode_init_once,fs/inode.c, 193}
Impressive, Bill!
How tightly is your work bound to -rt? Iow, any chance of separating the two? Or should we even want to?
Quoted 4 lines
The first column is the number of the times that object was contented against. The second is the number of times this lock object was initialized. The third is the annotation scheme that directly attaches the lock object (spinlock, etc..) in line with the function initializer to avoid the binary tree lookup.
I don't entirely get the third item, can you elaborate a bit?
Do you have a feeling of the runtime overhead?
Thanks.
Signature · 2 lines
http://www.PowerDNS.com Open source, database driven DNS Software http://netherlabs.nl Open and Closed source services
Quoted 9 lines · bert hubert
Quoted 2 lines · Bill Huey
[8264, 996648, 0] {
inode_init_once,fs/inode.c, 196}
[8552, 996648, 0] {inode_init_once,fs/inode.c, 193}Impressive, Bill!
How tightly is your work bound to -rt? Iow, any chance of separating the two? Or should we even want to?
Right now, it's solely dependent on -rt, but the basic mechanisms of how it works is pretty much the same as lockdep. Parts of it should be moveable across to regular kernels. The only remaining parts would be altering the lock structure (spinlock, mutex, etc...) to have a pointer that it can use to do the statistical tracking. If it's NULL then it's dunamically allocated and handled differently and allocated when the lock is contended against.
There's other uses for it as well. Think about RCU algorithms that need to spin-try to make sure the update of an element or the validation of it's data is safe to do. If an object was created to detect those spins it'll track what is effectively contention as well as it is represented in that algorithm. I've seen an RCU radix tree implementation do something like that.
Quoted 6 lines
Quoted 4 lines
The first column is the number of the times that object was contented against. The second is the number of times this lock object was initialized. The third is the annotation scheme that directly attaches the lock object (spinlock, etc..) in line with the function initializer to avoid the binary tree lookup.
I don't entirely get the third item, can you elaborate a bit?
I hate the notion of a search, so I directly set the pointer to a object that's statically defined. It means that the object is directly connected to what is suppose to backing it without doing a runtime search. When that's done, all of the numbers from the second column get moved to the third.
Quoted 1 line
Do you have a feeling of the runtime overhead?
There's minimal runtime overhead I believe since it's only doing an atomic increment of the stats during the slowpath before the thread is actually shoved into a wait queue. That's something that happpens seldomly.
bill
Quoted 10 lines · Bill Huey
Quoted 2 lines · bert hubert
How tightly is your work bound to -rt? Iow, any chance of separating the two? Or should we even want to?
There's other uses for it as well. Think about RCU algorithms that need to spin-try to make sure the update of an element or the validation of it's data is safe to do. If an object was created to detect those spins it'll track what is effectively contention as well as it is represented in that algorithm. I've seen an RCU radix tree implementation do something like that.
That was a horrible paragraph plus I'm bored at the moment. What I meant is that lockless algorithms occasionally have a spin-try associated with it as well that might possibly validate the data that's updated against the entire data structure for some kind of consistency cohernecy or possibly on an individual element. That retry or spin can be considered a contention as well and it can be made aware to this lock-stat patch just by connecting the actually occurance of retry logic against a backing object.
I need to be more conscious about proofreading what I write before sending it off. Was this clear ?
bill