From 0c52a8435aa399781856869daa7ef30cef14fad5 Mon Sep 17 00:00:00 2001 From: Scott Wood Date: Tue, 20 Mar 2007 08:35:22 -0500 Subject: [PATCH] xfer to laptop --- include/c++/util/handle.h | 147 ++++++++++++++++++++++++++++++++++++++ include/c++/util/radix.h | 126 ++++++++++++++++++++++++++++++++ include/c/std/string.h | 1 + kernel/include/kern/orb.h | 4 +- kernel/orb/invoke.cc | 7 +- 5 files changed, 278 insertions(+), 7 deletions(-) create mode 100644 include/c++/util/handle.h create mode 100644 include/c++/util/radix.h diff --git a/include/c++/util/handle.h b/include/c++/util/handle.h new file mode 100644 index 0000000..b22648e --- /dev/null +++ b/include/c++/util/handle.h @@ -0,0 +1,147 @@ +// Radix trees. Supports mapping from integer keys to objects, and optionally +// + To allow +// lockless lookups, the radix tree nodes are only added, never removed. The +// caller must ensure the synchronization of allocation and deallocation. +// +// Written by Scott Wood . +// +// This software is provided 'as-is', without any express or implied warranty. +// In no event will the authors or contributors be held liable for any damages +// arising from the use of this software. +// +// This software is in the public domain. + +#ifndef _UTIL_RADIX_H +#define _UTIL_RADIX_H + +#include +#include +#include + +#include + +namespace Util { + template + struct Handle { + T *ptr; + }; + + template + struct RefHandle : public Handle { + unsigned int ref; + }; + + // Each node in the tree will contain 2**radix_bits handles. + template + class RadixTree { + typedef unsigned int Key; + + enum { + node_size = 1 << radix_bits, + long_bits = sizeof(unsigned long) * 8; + bitmap_len = (node_size - 1) / long_bits + 1, + twolevel_bitmap = bitmap_len > 4 + }; + + struct NodeBase { + int shift; + unsigned long bmap[bitmap_len + twolevel_bitmap]; + + NodeBase() + { + memset(bmap, 0, sizeof(bmap)); + } + + // Find the first free entry in this node. + // Returns -1 if none found. + int find_first() + { + if (twolevel_bitmap) { + if (~bmap[0] == 0) + return -1; + + return ll_ffs(~bmap[ll_ffs(~bmap[0]) + 1]); + } + + return ll_multiword_ffc(bmap, 0, node_size); + } + }; + + struct Node : public NodeBase { + T handles[node_size]; + + Node() + { + shift = 0; + memset(handles, 0, sizeof(handles)); + } + }; + + struct DirNode : public NodeBase { + void *ptrs[node_size]; + + DirNode(int SHIFT) : shift(SHIFT) + { + memset(ptrs, 0, sizeof(ptrs)); + } + }; + + NodeBase *toplevel; + + static int key_to_offset(Key key, int shift) + { + return (key >> shift) & (node_size - 1); + } + + public: + T *lookup(Key key, bool add = false) + { + Node *node = toplevel; + + while (unlikely(!toplevel || key_to_offset(key, toplevel->shift + + radix_bits) != 0)) + { + if (!add) + return NULL; + + if (!toplevel) { + toplevel = new Node; + } else { + Node *new_node = new DirNode(toplevel->shift + radix_bits); + new_node->ptrs[0] = toplevel; + toplevel = new_node; + } + } + + while (shift >= radix_bits) { + int off = key_to_offset(key, shift); + void *new_node = static_cast(node)[off]; + + if (!new_node) { + if (!add) + return NULL; + + new_node = Mem::alloc_pages(1); + memset(new_node, 0, Arch::page_size); + static_cast(node)[off] = new_node; + } + + shift -= dir_shift; + node = new_node; + } + + assert(shift == 0); + return static_cast(node) + key_to_offset(key, 0); + } + + RadixTree() + { + toplevel = Mem::alloc_pages(1); + memset(toplevel, 0, Arch::page_size); + depth = 0; + } + }; +} + +#endif diff --git a/include/c++/util/radix.h b/include/c++/util/radix.h new file mode 100644 index 0000000..b75d27e --- /dev/null +++ b/include/c++/util/radix.h @@ -0,0 +1,126 @@ +// Generic radix trees, which supports mapping integer keys to objects. +// +// Written by Scott Wood . +// +// This software is provided 'as-is', without any express or implied warranty. +// In no event will the authors or contributors be held liable for any damages +// arising from the use of this software. +// +// This software is in the public domain. + +#ifndef _UTIL_RADIX_H +#define _UTIL_RADIX_H + +#include +#include +#include + +#include + +namespace Util { + // Each leaf node in the tree will contain 2**radix_bits handles. + // Each directory node will contain 2**dir_bits pointers. + template + class RadixTree { + typedef unsigned int Key; + + enum { + node_size = 1 << radix_bits, + dir_size = 1 << dir_bits, + long_bits = sizeof(unsigned long) * 8, + }; + + struct Node { + const int shift; + + protected: + Node(int SHIFT) : shift(SHIFT) + { + } + }; + + struct LeafNode : public Node { + T handles[node_size]; + + LeafNode() : Node(0) + { + shift = 0; + memset(handles, 0, sizeof(handles)); + } + }; + + struct DirNode : public Node { + Node *ptrs[node_size]; + + DirNode(int shift) : Node(shift) + { + memset(ptrs, 0, sizeof(ptrs)); + } + }; + + Node *toplevel; + + static int key_to_dir_offset(Key key, int shift) + { + return (key >> shift) & (dir_size - 1); + } + + static uint key_to_offset(Key key) + { + return key & (node_size - 1); + } + + public: + T *lookup(Key key, bool add = false) + { + int next_shift = toplevel->shift == 0 ? radix_bits : dir_bits; + + while (unlikely(key_to_dir_offset(key, toplevel->shift + + next_shift) != 0)) + { + if (!add) + return NULL; + + Node *new_node = new DirNode(toplevel->shift + next_shift); + new_node->ptrs[0] = toplevel; + toplevel = new_node; + next_shift = dir_bits; + } + + Node *node = toplevel; + + while (node->shift >= radix_bits) { + int off = key_to_dir_offset(key, node->shift); + NodeBase *new_node = node[off]; + + shift == 0 ? new LeafNode + : new DirNode(shift); + void *new_node = static_cast(node)[off]; + + if (!new_node) { + if (!add) + return NULL; + + new_node = Mem::alloc_pages(1); + memset(new_node, 0, Arch::page_size); + static_cast(node)[off] = new_node; + } + + shift -= dir_shift; + node = new_node; + } + + assert(shift == 0); + return static_cast(node) + key_to_offset(key, 0); + } + + RadixTree() + { + toplevel = new LeafNode; + memset(toplevel, 0, Arch::page_size); + depth = 0; + } + }; +} + +#endif diff --git a/include/c/std/string.h b/include/c/std/string.h index 33cd4a7..31323c6 100644 --- a/include/c/std/string.h +++ b/include/c/std/string.h @@ -7,6 +7,7 @@ extern "C" { #endif +void *memset(void *block, int count, size_t len); int memcmp(const void *b1, const void *b2, size_t len); size_t strlen(const char *s); diff --git a/kernel/include/kern/orb.h b/kernel/include/kern/orb.h index b00d758..e420fc7 100644 --- a/kernel/include/kern/orb.h +++ b/kernel/include/kern/orb.h @@ -81,11 +81,11 @@ namespace ORB { class IDSpace { // Reverse mapping of object pointers to local IDs - IDRMap id_rmap; + IDRMap idrmap; public: Object *lookup(u32 id); - u32 rlookup(Object *obj); + ObjectHdr *get_local_hdr(Object *obj); }; } diff --git a/kernel/orb/invoke.cc b/kernel/orb/invoke.cc index 2e1440f..27a1ebe 100644 --- a/kernel/orb/invoke.cc +++ b/kernel/orb/invoke.cc @@ -47,17 +47,14 @@ namespace ORB { return &hdr->frames[++thread->orbstack_top]; } - u32 IDSpace::rlookup(Object *obj) + ObjectHdr *IDSpace::get_local_hdr(Object *obj) { -#if 0 - ObjectHdr *hdr = idtree.find(obj); + ObjectHdr *hdr = idrmap.lookup(obj->id); if (!hdr) return 0; return hdr->id; -#endif - return 0; } } -- 2.39.2