Date: Wed, 31 Mar 2004 22:36:33 -0800 (PST) From: Marcel Moolenaar <marcel@FreeBSD.org> To: Perforce Change Reviews <perforce@freebsd.org> Subject: PERFORCE change 50101 for review Message-ID: <200404010636.i316aXe0029946@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=50101 Change 50101 by marcel@marcel_nfs on 2004/03/31 22:35:42 Implement some thread ID allocator. The fundamental properties if the allocator are (or are assumed to be): o Allocation of thread IDs must be fast, o Immediate reuse of TIDs is not a problem because the TIDs are only used in corefiles and for kernel debugging. The allocator maintains a list of bitmaps. Each bitmap tracks 1024 TIDs. When all bitmaps are "full", the allocator creates a new bitmap. When threads are destroyed, TIDs are freed in the bitmap. Empty bitmaps are currently not destroyed. The allocator is not tuned or even perfect. It works (AFAICT), so it should suffice. Affected files ... .. //depot/projects/gdb/sys/kern/kern_thread.c#7 edit Differences ... ==== //depot/projects/gdb/sys/kern/kern_thread.c#7 (text+ko) ==== @@ -133,6 +133,32 @@ "debug virtual cpus"); /* + * Thread ID allocator. The allocator keeps track of assigned IDs by + * using a bitmap. The bitmap is created in parts. The parts are linked + * together. + */ +typedef u_long tid_bitmap_word; + +#define TID_IDS_PER_PART 1024 +#define TID_IDS_PER_IDX (sizeof(tid_bitmap_word) << 3) +#define TID_BITMAP_SIZE (TID_IDS_PER_PART / TID_IDS_PER_IDX) +#define TID_MIN (PID_MAX + 1) + +struct tid_bitmap_part { + STAILQ_ENTRY(tid_bitmap_part) bmp_next; + tid_bitmap_word bmp_bitmap[TID_BITMAP_SIZE]; + int bmp_base; + int bmp_free; +}; + +static STAILQ_HEAD(, tid_bitmap_part) tid_bitmap = + STAILQ_HEAD_INITIALIZER(tid_bitmap); +static uma_zone_t tid_zone; + +struct mtx tid_lock; +MTX_SYSINIT(tid_lock, &tid_lock, "TID lock", MTX_DEF); + +/* * Prepare a thread for use. */ static void @@ -141,6 +167,7 @@ struct thread *td; td = (struct thread *)mem; + td->td_tid = 0; td->td_state = TDS_INACTIVE; td->td_oncpu = NOCPU; td->td_critnest = 1; @@ -152,10 +179,28 @@ static void thread_dtor(void *mem, int size, void *arg) { - struct thread *td; + struct thread *td; + struct tid_bitmap_part *bmp; + int bit, idx, tid; td = (struct thread *)mem; + if (td->td_tid > PID_MAX) { + STAILQ_FOREACH(bmp, &tid_bitmap, bmp_next) { + if (td->td_tid >= bmp->bmp_base && + td->td_tid < bmp->bmp_base + TID_IDS_PER_PART) + break; + } + KASSERT(bmp != NULL, "No TID bitmap?"); + mtx_lock(&tid_lock); + tid = td->td_tid - bmp->bmp_base; + idx = tid / TID_IDS_PER_IDX; + bit = 1UL << (tid % TID_IDS_PER_IDX); + bmp->bmp_bitmap[idx] |= bit; + bmp->bmp_free++; + mtx_unlock(&tid_lock); + } + #ifdef INVARIANTS /* Verify that this thread is in a safe state to free. */ switch (td->td_state) { @@ -861,6 +906,8 @@ thread_zone = uma_zcreate("THREAD", sched_sizeof_thread(), thread_ctor, thread_dtor, thread_init, thread_fini, UMA_ALIGN_CACHE, 0); + tid_zone = uma_zcreate("TID", sizeof(struct tid_bitmap_part), + NULL, NULL, NULL, NULL, UMA_ALIGN_CACHE, 0); ksegrp_zone = uma_zcreate("KSEGRP", sched_sizeof_ksegrp(), NULL, NULL, ksegrp_init, NULL, UMA_ALIGN_CACHE, 0); @@ -1032,14 +1079,50 @@ } /* - * Assign a thread ID between 100000 and 999999. + * Assign a thread ID. */ int thread_new_tid(void) { - static int next_tid = 100000; + struct tid_bitmap_part *bmp, *new; + int bit, idx, tid; + + mtx_lock(&tid_lock); + STAILQ_FOREACH(bmp, &tid_bitmap, bmp_next) { + if (bmp->bmp_free) + break; + } + /* Create a new bitmap if we run out of free bits. */ + if (bmp == NULL) { + mtx_unlock(&tid_lock); + new = uma_zalloc(tid_zone, M_WAITOK); + mtx_lock(&tid_lock); + bmp = STAILQ_LAST(&tid_bitmap, tid_bitmap_part, bmp_next); + if (bmp == NULL || bmp->bmp_free < TID_IDS_PER_PART/2) { + /* 1=free, 0=assigned. This way we can use ffsl(). */ + memset(new->bmp_bitmap, ~0U, sizeof(new->bmp_bitmap)); + new->bmp_base = (bmp == NULL) ? TID_MIN : + bmp->bmp_base + TID_IDS_PER_PART; + new->bmp_free = TID_IDS_PER_PART; + STAILQ_INSERT_TAIL(&tid_bitmap, new, bmp_next); + bmp = new; + new = NULL; + } + } else + new = NULL; + /* We have a bitmap with available IDs. */ + idx = 0; + while (idx < TID_BITMAP_SIZE && bmp->bmp_bitmap[idx] == 0UL) + idx++; + bit = ffsl(bmp->bmp_bitmap[idx]) - 1; + tid = bmp->bmp_base + idx * TID_IDS_PER_IDX + bit; + bmp->bmp_bitmap[idx] &= ~(1UL << bit); + bmp->bmp_free--; + mtx_unlock(&tid_lock); - return (next_tid++); + if (new != NULL) + uma_zfree(tid_zone, new); + return (tid); } /*
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200404010636.i316aXe0029946>