POSIX clocks & timers - more choices
A message that is not in the archive (sent off-list or not yet received): [email protected]
Review
Quoted 2 lines · Jim Houston
(quoted diff) +2
-0+struct id_layer { + unsigned int bitmap: (1<<ID_BITS);
The bitfield is a bit weird here and the compiler will pad the field anyways always to unsigned int because of the aligned pointer next. It could potentially generate bad code. What's the rationale ?
Review
Quoted 6 lines
(quoted diff) +5
-0+ struct id_layer *ary[1<<ID_BITS]; +void *id_lookup(struct id *idp, int id); +int id_new(struct id *idp, void *ptr); +void id_remove(struct id *idp, int id); +void id_init(struct id *idp, int min_wrap);
Looks a bit like namespace pollution. Perhaps a bit more descriptive names ?
Review
Quoted 2 lines
(quoted diff) +2
-0+{ + if (p->ary[bit] && p->ary[bit]->bitmap == (typeof(p->bitmap))-1)
Without bitfield this would look much less weird.
I would recommend using the bitops.h primitives for such stuff anyways.
Review
Quoted 10 lines
+ * Since we can't allocate memory with spinlock held and dropping the
+ * lock to allocate gets ugly keep a free list which will satisfy the
+ * worst case allocation.
+ */(quoted diff) +6
-0+ +struct id_layer *id_free; +int id_free_cnt; + +static inline struct id_layer *alloc_layer(void) +{
Standard way would be a mempool. Or better
preallocation before you get the locks.
Review
Quoted 4 lines
(quoted diff) +4
-0+ if (id <= 0) + return(NULL); + id--; + spin_lock_irq(&id_lock);
Shouldn't this be irqsave ? Otherwise there could be hard to track down bugs later with this code turning on interrupts for other code by accident.
Overall I'm not sure all this radix tree stuff is worth the overhead and code complexity. Is just a bitmap with find_first_bit() and a last hit cache too slow ? How many timers do you expect to maintain ?
It looks like a similar problem to what kernel/pid.c does. If you're really determined to have an complicated implementation I would recommend seeing if you could share code with that.
Review
Quoted 3 lines
(quoted diff) +3
-0+struct k_clock { + struct timer_pq pq; + int res; /* in nano seconds */
Hopefully it never overflows.
Review
Quoted 2 lines
(quoted diff) +2
-0+ default: + printk(KERN_WARNING "sending signal failed: %d\n", ret);
printk should be removed or at least rate limited, because it could make the system unusable
Review
Quoted 13 lines
(quoted diff) +13
-0+/* + * For some reason mips/mips64 define the SIGEV constants plus 128. + * Here we define a mask to get rid of the common bits. The + * optimizer should make this costless to all but mips. + */ +#if (ARCH == mips) || (ARCH == mips64) +#define MIPS_SIGEV ~(SIGEV_NONE & \ + SIGEV_SIGNAL & \ + SIGEV_THREAD & \ + SIGEV_THREAD_ID) +#else +#define MIPS_SIGEV (int)-1 +#endif
This definitely needs to be cleaned up.
Review
Quoted 6 lines
(quoted diff) +6
-0+{ + struct task_struct * rtn = current; + + if (event->sigev_notify & SIGEV_THREAD_ID & MIPS_SIGEV ) { + if ( !(rtn = + find_task_by_pid(event->sigev_notify_thread_id)) ||
Are you holding any locks or how do you make sure rtn doesn't go away ?
Review
Quoted 7 lines
(quoted diff) +7
-0+ + +static struct k_itimer * alloc_posix_timer(void) +{ + struct k_itimer *tmr; + tmr = kmem_cache_alloc(posix_timers_cache, GFP_KERNEL); + memset(tmr, 0, sizeof(struct k_itimer));
Needs a NULL check.
Overall your code looks like overkill to me. I think it would be better to start with a simple implementation and only add all the complicated data structures if it should really be a bottle neck in some real world load. It also needs some cleanup to remove dead code etc.
-Andi
Quoted 11 lines · Andi Kleen
Review
Quoted 2 lines · Jim Houston
(quoted diff) +2
-0+struct id_layer { + unsigned int bitmap: (1<<ID_BITS);The bitfield is a bit weird here and the compiler will pad the field anyways always to unsigned int because of the aligned pointer next. It could potentially generate bad code. What's the rationale ?
Hi Andi,
Thanks for the review. I will try to answer your questions as inline.
The idea of declaring the bitmap with a field width was to give an error if ID_BITS was made larger than the sizeof(int). It would probably make more sense to set ID_BITS from sizeof(int) or use an array for the bitmap and allow an arbitrary value.
Quoted 9 lines
Review
Quoted 6 lines
(quoted diff) +5
-0+ struct id_layer *ary[1<<ID_BITS]; +void *id_lookup(struct id *idp, int id); +int id_new(struct id *idp, void *ptr); +void id_remove(struct id *idp, int id); +void id_init(struct id *idp, int min_wrap);Looks a bit like namespace pollution. Perhaps a bit more descriptive names ?
Coming up with good names is always hard. Here is what they mean what should they be called?
id_lookup - returns a pointer associated with an id value. id_new - allocates a new id. It returns the id and
saves the poiner in its data structure.id_remove - frees the id and breaks the association between
the id and the pointer.id_init - Initializes a "struct id" which is the basis for
this id translation.
Quoted 7 lines
Review
Quoted 3 lines
(quoted diff) +2
-0+{ + if (p->ary[bit] && p->ary[bit]->bitmap == (typeof(p->bitmap))-1)Without bitfield this would look much less weird.
I would recommend using the
bitops.hprimitives for such stuff anyways.
I will. This does look wierd, is this my code?
Quoted 14 lines
Review
Quoted 11 lines
+ * Since we can't allocate memory with spinlock held and dropping the
+ * lock to allocate gets ugly keep a free list which will satisfy the
+ * worst case allocation.
+ */(quoted diff) +6
-0+ +struct id_layer *id_free; +int id_free_cnt; + +static inline struct id_layer *alloc_layer(void) +{Standard way would be a mempool. Or better
preallocation before you get the locks.
I prototyped this code in user space and then started thinking about locking. How is what I'm doing different than pre-allocating before locking. I would still need to lock and re-check that I had enough data structures pre-allocated and loop.
Quoted 8 lines
Review
Quoted 4 lines
(quoted diff) +4
-0+ if (id <= 0) + return(NULL); + id--; + spin_lock_irq(&id_lock);Shouldn't this be irqsave ? Otherwise there could be hard to track down bugs later with this code turning on interrupts for other code by accident.
My assumption is that the id stuff would only be used from code where I know interrupts are enabled. Saving the flags wouldn't hurt though.
Quoted 7 lines
Overall I'm not sure all this radix tree stuff is worth the overhead and code complexity. Is just a bitmap with
find_first_bit()and a last hit cache too slow ? How many timers do you expect to maintain ?It looks like a similar problem to what
kernel/pid.cdoes. If you're really determined to have an complicated implementation I would recommend seeing if you could share code with that.
When I wrote it I had hoped that it could be used for get_pid. See my post:
http://marc.theaimsgroup.com/?l=linux-kernel&m=102916884821920&w=2
I guess the argument is that this approach is memory efficient and scales well for all possible id -> kernel pointer mappings.
Quoted 6 lines
Review
Quoted 4 lines
(quoted diff) +3
-0+struct k_clock { + struct timer_pq pq; + int res; /* in nano seconds */Hopefully it never overflows.
It better not its the resolution of the timer. Only a problem if Hz is less than 1.
Quoted 23 lines
Review
Quoted 3 lines
(quoted diff) +2
-0+ default: + printk(KERN_WARNING "sending signal failed: %d\n", ret);printk should be removed or at least rate limited, because it could make the system unusable
Review
Quoted 13 lines
(quoted diff) +13
-0+/* + * For some reason mips/mips64 define the SIGEV constants plus 128. + * Here we define a mask to get rid of the common bits. The + * optimizer should make this costless to all but mips. + */ +#if (ARCH == mips) || (ARCH == mips64) +#define MIPS_SIGEV ~(SIGEV_NONE & \ + SIGEV_SIGNAL & \ + SIGEV_THREAD & \ + SIGEV_THREAD_ID) +#else +#define MIPS_SIGEV (int)-1 +#endifThis definitely needs to be cleaned up.
Quoted 9 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+{ + struct task_struct * rtn = current; + + if (event->sigev_notify & SIGEV_THREAD_ID & MIPS_SIGEV ) { + if ( !(rtn = + find_task_by_pid(event->sigev_notify_thread_id)) ||Are you holding any locks or how do you make sure rtn doesn't go away ?
Good point. It looks like find_task_by_pid() needs to be protected by a read_lock(&tasklist_lock). The timers are linked into a list so they will be removed when the process exits. Any sugestions on a code example that does this right are welcome:-)
Quoted 9 lines
Review
Quoted 7 lines
(quoted diff) +7
-0+ + +static struct k_itimer * alloc_posix_timer(void) +{ + struct k_itimer *tmr; + tmr = kmem_cache_alloc(posix_timers_cache, GFP_KERNEL); + memset(tmr, 0, sizeof(struct k_itimer));Needs a NULL check.
O.K. You caught me being lazy. I have the same problem in the id code as well.
Quoted 8 lines
Overall your code looks like overkill to me. I think it would be better to start with a simple implementation and only add all the complicated data structures if it should really be a bottle neck in some real world load. It also needs some cleanup to remove dead code etc.
-Andi
Thanks for the review.
Jim Houston - Concurrent Computer Corp.
Quoted 8 lines · Jim Houston
Quoted 6 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+{ + if (p->ary[bit] && p->ary[bit]->bitmap == (typeof(p->bitmap))-1)Without bitfield this would look much less weird.
I would recommend using the
bitops.hprimitives for such stuff anyways.I will. This does look wierd, is this my code?
The typeof() cast looks weird. I had to think twice to make sense of it.
Quoted 5 lines
Good point. It looks like
find_task_by_pid()needs to be protected by aread_lock(&tasklist_lock). The timers are linked into a list so they will be removed when the process exits. Any sugestions on a code example that does this right are welcome:-)
/proc does it by increasing the count in the struct page of the stack page of the process. exit() knows about that. Example is somewhere in fs/proc/ The increase has to be done inside the lock. As always one has to be careful with lock ordering.
The standard way is to just hold the read lock of the tasklist.
-Andi
Andi Kleen wrote:
~snip~
Since he picked this up from my code...
Quoted 17 lines
Quoted 4 lines
(quoted diff) +3
-0+/* + * For some reason mips/mips64 define the SIGEV constants plus 128. + * Here we define a mask to get rid of the common bits. TheReview
Quoted 10 lines
(quoted diff) +10
-0+ * optimizer should make this costless to all but mips. + */ +#if (ARCH == mips) || (ARCH == mips64) +#define MIPS_SIGEV ~(SIGEV_NONE & \ + SIGEV_SIGNAL & \ + SIGEV_THREAD & \ + SIGEV_THREAD_ID) +#else +#define MIPS_SIGEV (int)-1 +#endifThis definitely needs to be cleaned up.
What do you suggest? Changing mips? I would like this number to go away also, but with the mips assignments it is a bit of a bother.
Signature · 5 lines
George Anzinger [email protected] High-res-timers: http://sourceforge.net/projects/high-res-timers/ Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml
Quoted 3 lines · george anzinger
What do you suggest? Changing mips? I would like this number to go away also, but with the mips assignments it is a bit of a bother.
Yes, mips should be probably changed or a new macro be defined.
-Andi