PERFORCE change 50101 for review

[Marcel Moolenaar]

http://perforce.freebsd.org/chv.cgi?CH=50101

Change 50101 by marcel at 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);
 }
 
 /*