For your inspection: small id pool
authorRon Minnich <rminnich@google.com>
Mon, 26 Jan 2015 23:40:55 +0000 (15:40 -0800)
committerRon Minnich <rminnich@google.com>
Mon, 26 Jan 2015 23:40:55 +0000 (15:40 -0800)
This is a stack and it's about 30 times faster than the current
tag allocator used in devmnt (yes, 30).

It could be used for any id pool that's less than 64K, including
VPID and the 16-bit tags used in VMID.

I doubt I need to use the first element of the array as a top of
stack, that's a little too cute maybe, but not returning element
0 is a good idea, that is reserved in many situation SUCH AS
vpid and so on.

Can we do some sort of ACAS on the TOS in such a way that it never
increments beyond 0xfffe?

Comments appreciated.

Signed-off-by: Ron Minnich <rminnich@google.com>
kern/drivers/dev/mnt.c
kern/include/smallidpool.h [new file with mode: 0644]
kern/kfs/ifconfig
kern/src/kmalloc.c
kern/src/monitor.c
kern/src/ns/chan.c
kern/src/smallidpool.c [new file with mode: 0644]

index 4a92f03..c661b95 100644 (file)
@@ -834,6 +834,7 @@ void mountio(struct mnt *m, struct mntrpc *r)
                        nexterror();
                }
                r = mntflushalloc(r, m->msize);
+               printk("FL\n");
                /* need one for every waserror call (so this plus one outside) */
                poperror();
        }
diff --git a/kern/include/smallidpool.h b/kern/include/smallidpool.h
new file mode 100644 (file)
index 0000000..a775e7f
--- /dev/null
@@ -0,0 +1,19 @@
+/* Copyright (c) 2015 Google Inc.
+ *
+ * Trivial ID pool for small sets of things (< 64K)
+ * implemented as a stack.
+ */
+
+#define MAXAMT 65535
+
+// Element 0 is top of stack pointer. It  initially points to 1.
+// You therefore can not get ID 0. The max id you can get is 65534,
+// due to the use of uint16_t for the stack elements. That covers just
+// about everything we've ever needed.
+// The check array is used instead of a bitfield because these architectures
+// suck at those.
+struct idpool {
+       unit16_t *ids;
+       unit8_t *check;
+       int size;
+};
index 4097b78..32c05af 100755 (executable)
@@ -169,7 +169,7 @@ then
                usleep 1000
        done
 fi
-mount -a \#s/cs /net
+#mount -a \#s/cs /net
 
 # this is noisy, so it is off by default.
 #echo debug > /net/cs
index 872a25f..1a94109 100644 (file)
@@ -56,6 +56,14 @@ void *kmalloc(size_t size, int flags)
        void *buf;
        int cache_id;
        // determine cache to pull from
+       if (0)
+       if ((size < 9 ) && (!printx_on)) {
+               extern bool printx_on;
+               printx_on = 1;
+               printk("alloc one lousy 64-bit int? \n");
+               monitor(NULL);
+               printx_on = 0;
+       }
        if (ksize <= KMALLOC_SMALLEST)
                cache_id = 0;
        else
index 14af76b..ccada47 100644 (file)
@@ -286,6 +286,10 @@ static void print_info_handler(struct hw_trapframe *hw_tf, void *data)
        cprintf("MTRR Phys7 Base = 0x%016llx, Mask = 0x%016llx\n",
                read_msr(0x20e), read_msr(0x20f));
 #endif // CONFIG_X86
+#ifdef CONFIG_SYSCALL_STRING_SAVING
+       cprintf("syscall string: %s\n",
+               per_cpu_info[core_id()].cur_kthread->name);
+#endif
        cprintf("----------------------------\n");
        spin_unlock_irqsave(&print_info_lock);
 }
index 4891f95..b9b7864 100644 (file)
@@ -1382,6 +1382,8 @@ void validname(char *aname, int slashok)
                        name += chartorune(&r, name);
 #endif
                if (c >= 0x7f) {
+                       printk("Akaros doesn't do UTF-8");
+                       monitor(NULL);
                        error("Akaros doesn't do UTF-8");
                } else {
                        if (isfrog[c])
diff --git a/kern/src/smallidpool.c b/kern/src/smallidpool.c
new file mode 100644 (file)
index 0000000..830eb3b
--- /dev/null
@@ -0,0 +1,60 @@
+/* Copyright (c) 2015 Google Inc.
+ *
+ * Trivial ID pool for small sets of things (< 64K)
+ * implemented as a stack.
+ */
+
+struct idpool *init(int size)
+{
+       int i;
+       struct idpool *id;
+       if (size > MAXAMT)
+               return NULL;
+       id = malloc(sizeof(*id) + 2*(size+1) + (size + 1));
+       id->size = size;
+       id->ids = (void *)&id[1];
+       id->check = (void *)&id->ids[id->size + 1];
+       for(i = 0; i < id->size+1; i++) {
+               id->ids[i] = i;
+               // fe rhymes with "free"
+               id->check[i] = 0xfe;
+       }
+       // set tos.
+       id->ids[0] = 1;
+       return id;
+}
+
+
+int pop(struct idpool *id)
+{
+       int tos, v;
+       if (id->ids[0] == id->size) {
+               return -1;
+       }
+       /* NOT SMP SAFE! CAN'T USE IT YET!
+        * the intent here is that we want to be able to atomic ops on the stack pointer
+        * and avoid locking. One way might be to load it and, if it's in range, do a CAS.
+        */
+       tos = id->ids[0];
+       id->ids[0]++;
+       v = id->ids[tos];
+       if (id->check[v] != 0xfe) {
+               printk("BAD! %d is already allocated (0x%x)\n", v, id->check[v]);
+               return -1;
+       }
+       id->check[v] = 0x5a;
+       return v;
+}
+
+void push(struct idpool *id, int v)
+{
+       int tos;
+       if (id->check[v] != 0x5a) {
+               panic("BAD! freeing non-allocated: %d(0x%x)\n", v, id->check[v]);
+               return;
+       }
+       id->ids[0]--;
+       tos = id->ids[0];
+       id->ids[tos] = v;
+       id->check[v] = 0xfe;
+}