diff options
| -rw-r--r-- | src/ChangeLog | 5 | ||||
| -rw-r--r-- | src/utils/Makefile.in | 2 | ||||
| -rw-r--r-- | src/utils/storage.H | 197 | ||||
| -rw-r--r-- | src/utils/storage.cc | 129 |
4 files changed, 182 insertions, 151 deletions
diff --git a/src/ChangeLog b/src/ChangeLog index 5ab6497f..da1e4e31 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,8 @@ +2011-03-17 Gabriel Dos Reis <gdr@cs.tamu.edu> + + * utils/storage.H: Rework. + * utils/storage.cc: Likewise. + 2011-03-16 Gabriel Dos Reis <gdr@cs.tamu.edu> * interp/i-syscmd.boot (compileSpad2Cmd): Remove experimental diff --git a/src/utils/Makefile.in b/src/utils/Makefile.in index 764bda0f..e4211f62 100644 --- a/src/utils/Makefile.in +++ b/src/utils/Makefile.in @@ -87,7 +87,7 @@ stamp-headers: $(libOpenAxiom_HEADERS) Makefile done ; \ $(STAMP) stamp-headers -hammer$(EXEEXT): $(hammer_OBJECTS) libOpenAxiom.$(LIBEXT) +hammer$(EXEEXT): $(bin_PROGRAMS) libOpenAxiom.$(LIBEXT) $(CXXLINK) -o $@ $(hammer_OBJECTS) $(hammer_LDADD) $(LDFLAGS) libOpenAxiom.$(LIBEXT): $(libOpenAxiom_OBJECTS) diff --git a/src/utils/storage.H b/src/utils/storage.H index 29da96eb..ab334abb 100644 --- a/src/utils/storage.H +++ b/src/utils/storage.H @@ -1,4 +1,4 @@ -// Copyright (C) 2010, Gabriel Dos Reis. +// Copyright (C) 2010-2011, Gabriel Dos Reis. // All rights reserved. // // Redistribution and use in source and binary forms, with or without @@ -52,7 +52,7 @@ namespace OpenAxiom { // Objects of (type derived from) this type are used to report // error orignating from the OpenAxiom core system. struct SystemError { - explicit SystemError(std::string); + explicit SystemError(const std::string&); virtual ~SystemError(); // Return the text of the diagnostic message. virtual const std::string& message() const; @@ -61,7 +61,7 @@ namespace OpenAxiom { }; // Report a file system error - void filesystem_error(std::string); + void filesystem_error(const std::string&); namespace Memory { // Datatype for the unit of storage. @@ -99,44 +99,28 @@ namespace OpenAxiom { // This class is a low-level abstraction intented for use // to implement higher level storage abstraction. struct Storage { - // Acquire storage chunk of at least `n' bytes, and align - // the first allocatable address to `a' boundary. - // The result is a pointer to a storage object. That object - // `result' is constructed such that `result->free' points - // to the next allocatable address, with alignment `a'. - // After allocation, the real capacity of the allocated - // object is reported by `result->capacity()'. - static Storage* acquire(size_t a, size_t n); + // Objects of this sbstract datatype holds storage objects. + struct Handle; + // Acquire storage chunk of at least `n' bytes. + // The result is a pointer to a storage object. That object + // `result' is constructed such that `begin(result)' points + // to the next allocatable address. + static Handle* acquire(size_t n); + // Return the storage pointed to by the operand. It // must be a pointer value previously returned by `acquire'. // Otherwise, the result is undefined. - static void release(Storage*); - - // Count of bytes that can fit in this storage. - size_t capacity() const { return limit_bot - limit_top; } - - // Count of available allocatable bytes in this storage. - size_t room() const { return limit_bot - free; } - - // Count of used bytes in this storage. - size_t occupancy() const { return free - limit_top; } - - // Align next allocatable address to boundary given by operand. - // Return true on success, otherwise false. - bool align_to(size_t); - - // Allocate `n' bytes from this storage. It is assumed that prior - // to calling this function, `n' is less than `room()'. - // The allocated storage is guaranteed to contain only zeros. - void* allocate(size_t); - - // Next unused address - void* next_available() { return free; } - - // address at offset `off' from the first allocatable address. - void* at_offset(size_t off) { - return limit_top + off; + static void release(Handle*); + + // Return the start address of storage area. + // Note: this should not be confused with the address of + // the handle object. + static Pointer begin(Handle*); + + // Courtesy conversion function from pointer to byte address. + static Byte* byte_address(Pointer h) { + return static_cast<Byte*>(h); } // Round up `n' to a multiple of `a', a power of 2. @@ -144,35 +128,41 @@ namespace OpenAxiom { round_up(size_t n, size_t a) { return (n + a - 1) & ~(a - 1); } + }; - // Next address after `p' in this storage that has alignment `a'. - void* - round_up(void* p, size_t a) { - return base() + round_up(base() - static_cast<Byte*>(p), a); - } + // ------------------------- + // -- SinglyLinkedStorage -- + // ------------------------- + // This class implements a simple single-linked list of storage + // objects. + struct SinglyLinkedStorage : Storage { + // Same as Storage::acquire, except begin(h) returns an address + // that satisfies the alignment requirement `a'. + static Handle* acquire(size_t n, size_t a); - protected: - Byte* limit_top; // first allocatable address - Byte* limit_bot; // one-past-the-end of valid allocatable - // address in this storage. - Byte* free; // first allocatable address suitably - // aligned at boundary specified at - // construction time. - - Storage() { } - - // Address of the host OS page holding this storage. - Byte* base() { - return reinterpret_cast<Byte*>(this); - } - - size_t extent() { - return size_t(limit_bot - base()); - } + // Return the previous handle in the link chain. + static Handle*& previous(Handle*); + }; - private: - Storage(const Storage&); // not implemented - Storage& operator=(const Storage&); // idem. + // ------------------ + // -- BlockStorage -- + // ------------------ + // This class implements a simple single-linked list of block storage. + // Each block maintains information about the next allocatable + // address within that block. + struct BlockStorage : SinglyLinkedStorage { + // Same as SinglyLinkedStorage::acquire(); initialize internal + // bookkeepking machinery. + static Handle* acquire(size_t n, size_t a); + + // Return the next allocatable address within the given block. + static Pointer next_address(Handle*); + + // Return the amount of allocatable byte in the given block. + static size_t room(Handle*); + + // Set `n' bytes aside with the given storage block. + static Pointer book(Handle*, size_t); }; // ----------- @@ -184,7 +174,7 @@ namespace OpenAxiom { // it is guaranteed that objects allocated in a single call // to `allocate()' occupy a contiguous block of storage. template<typename T> - struct Arena { + struct Arena : protected BlockStorage { // Acquire storage capable of holding `n' objects of type `T'. explicit Arena(size_t); // Release all storage acquired by this object, upon end of life. @@ -196,39 +186,29 @@ namespace OpenAxiom { protected: // Address of the first object of type `T' in a storage. - static T* first_object(Storage* s) { - return static_cast<T*> - (s->round_up(&previous(s) + 1, openaxiom_alignment(T))); + static T* first_object(Handle* h) { + return static_cast<T*>(BlockStorage::begin(h)); } // Address of one-past-the-end object of type `T' in this storage. - static T* last_object(Storage* s) { - return static_cast<T*>(s->next_available()); + static T* last_object(Handle* h) { + return static_cast<T*>(BlockStorage::next_address(h)); } // Number of objects allocated in a storage. - static size_t object_count(Storage* s) { - return last_object(s) - first_object(s); - } - - // The `previous' link in the chain of storage. - static Storage*& previous(Storage* s) { - return *static_cast<Storage**>(s->at_offset(0)); + static size_t object_count(Handle* h) { + return last_object(h) - first_object(h); } - Storage* store; // active storage to allocate from - - private: - // Acquire storage large enough to hold `n' objects of type `T'. - static Storage* acquire(size_t); + BlockStorage::Handle* store; // active storage to allocate from }; template<typename T> size_t Arena<T>::population() const { size_t n = 0; - for (Storage* s = store; s != 0; s = previous(s)) - n += object_count(s); + for (Handle* h = store; h != 0; h = previous(h)) + n += object_count(h); return n; } @@ -236,48 +216,41 @@ namespace OpenAxiom { T* Arena<T>::allocate(size_t n) { const size_t sz = n * sizeof(T); - if (store->room() < sz) { - Storage* s = acquire(std::max(n, object_count(store))); - previous(s) = store; - store = s; + if (BlockStorage::room(store) < sz) { + // Not enough room left. Make sure we allocate storage + // at least as big as the current. + Handle* h = acquire(std::max(n, object_count(store)), + openaxiom_alignment(T)); + previous(h) = store; + store = h; } - return static_cast<T*>(store->allocate(sz)); + return static_cast<T*>(BlockStorage::book(store, sz)); } template<typename T> - Arena<T>::Arena(size_t n) : store(acquire(n)) { } + Arena<T>::Arena(size_t n) + : store(BlockStorage::acquire(n * sizeof (T), + openaxiom_alignment (T))) + { } template<typename T> Arena<T>::~Arena() { // Release storage in the reverse order of their // their allocation. while (store != 0) { - Storage* current = store; - store = previous(store); - Storage::release(current); + Handle* current = store; + store = BlockStorage::previous(store); + BlockStorage::release(current); } } - template<typename T> - Storage* - Arena<T>::acquire(size_t n) { - // We build single-linked list of Storage objects, so - // don't forget to account for the additional pointer, - // and necessary padding. - const size_t sz = n * sizeof(T) - + Storage::round_up(sizeof(Storage*), openaxiom_alignment(T)); - Storage* s = Storage::acquire(openaxiom_alignment(Storage*), sz); - s->allocate(sizeof(Storage*)); - previous(s) = 0; - s->align_to(openaxiom_alignment(T)); - return s; - } - // ------------- // -- Factory -- // ------------- template<typename T> struct Factory : Arena<T> { + typedef typename Arena<T>::Handle Handle; + Factory() : Arena<T>(nominal_population()) { } ~Factory(); @@ -307,21 +280,17 @@ namespace OpenAxiom { private: // Return 1 or the number of objects that can fit in a page unit. static size_t nominal_population() { - const size_t overhead = - Storage::round_up(sizeof(Storage), - openaxiom_alignment(Storage*)) - + Storage::round_up(sizeof(Storage*), openaxiom_alignment(T)); const size_t psz = page_size(); - if (overhead + sizeof (T) > psz) + if (sizeof (T) > psz) return 1; - return (psz - overhead) / sizeof(T); + return psz / sizeof(T); } }; // Destroy objects in the reverse order of their construction. template<typename T> Factory<T>::~Factory() { - for (Storage* s = this->store; s != 0; s = Arena<T>::previous(s)) { + for (Handle* s = this->store; s != 0; s = Arena<T>::previous(s)) { T* last = Arena<T>::last_object(s); for (--last; last >= Arena<T>::first_object(s); --last) last->~T(); diff --git a/src/utils/storage.cc b/src/utils/storage.cc index 0bd9265d..f7c2aec3 100644 --- a/src/utils/storage.cc +++ b/src/utils/storage.cc @@ -1,4 +1,4 @@ -// Copyright (C) 2010, Gabriel Dos Reis. +// Copyright (C) 2010-2011, Gabriel Dos Reis. // All rights reserved. // // Redistribution and use in source and binary forms, with or without @@ -62,7 +62,7 @@ namespace OpenAxiom { // ---------------- // -- SystemError -- // ---------------- - SystemError::SystemError(std::string s) : text(s) { } + SystemError::SystemError(const std::string& s) : text(s) { } SystemError::~SystemError() { } @@ -72,7 +72,7 @@ namespace OpenAxiom { } void - filesystem_error(std::string s) { + filesystem_error(const std::string& s) { throw SystemError(s); } @@ -130,43 +130,100 @@ namespace OpenAxiom { // ------------- // -- Storage -- // ------------- - Storage* - Storage::acquire(size_t alignment, size_t byte_count) { - // Adjust for overhead, and page boundary. - byte_count = round_up(byte_count + sizeof(Storage), page_size()); - Storage* mem = new(os_acquire_raw_memory(byte_count)) Storage; - mem->limit_top = mem->base() + round_up(sizeof(Storage), alignment); - mem->limit_bot = mem->base() + byte_count; - mem->free = mem->limit_top; - return mem; + struct Storage::Handle { + size_t extent; + void* start; + }; + + static inline Pointer + storage_end(Storage::Handle* h) { + return Storage::byte_address(h) + h->extent; + } + + Storage::Handle* + Storage::acquire(size_t n) { + // Adjust for overhead, and to page boundary. + n = round_up(n + sizeof(Handle), page_size()); + Handle* h = static_cast<Handle*>(os_acquire_raw_memory(n)); + h->extent = n; + h->start = h + 1; + return h; } void - Storage::release(Storage* store) { - os_release_raw_memory(store, store->extent()); - } - - void* - Storage::allocate(size_t n) { - void* result = free; - free += n; - return memset(result, 0, n); - } - - bool - Storage::align_to(size_t alignment) { - if (alignment == 0) // protect against nuts - return true; - if (alignment == 1) // no preferred alignment at all - return true; - Byte* b = base(); - const size_t offset = round_up(free - b, alignment); - if (offset < size_t(limit_bot - b)) { - free = b + offset; - return true; - } - return false; // not enough room left + Storage::release(Handle* h) { + os_release_raw_memory(h, h->extent); + } + + Pointer + Storage::begin(Handle* h) { + return h->start; + } + + // ------------------------- + // -- SinglyLinkedStorage -- + // ------------------------- + struct SingleLinkHeader : Storage::Handle { + Handle* previous; + }; + + SinglyLinkedStorage::Handle*& + SinglyLinkedStorage::previous(Handle* h) { + return static_cast<SingleLinkHeader*>(h)->previous; + } + + SinglyLinkedStorage::Handle* + SinglyLinkedStorage::acquire(size_t n, size_t a) { + const size_t overhead = round_up(sizeof (SingleLinkHeader), a); + Handle* h = Storage::acquire(overhead + n); + h->start = byte_address (h) + overhead; + previous(h) = 0; + return h; + } + + // ------------------ + // -- BlockStorage -- + // ------------------ + struct BlockHeader : SingleLinkHeader { + Byte* available; + }; + + static inline BlockHeader* + block_header(BlockStorage::Handle* h) { + return static_cast<BlockHeader*>(h); + } + + BlockStorage::Handle* + BlockStorage::acquire(size_t n, size_t a) { + const size_t overhead = round_up(sizeof (BlockHeader), a); + // Tell SinglyLinkedStorage not to align; we do that here. + BlockHeader* h = block_header + (SinglyLinkedStorage::acquire(overhead + n, 1)); + // Remember the next available address to allocate from. + h->available = byte_address(h) + overhead; + // That is also where the actual object storage starts. + h->start = h->available; + return h; + } + + Pointer + BlockStorage::next_address(Handle* h) { + return block_header(h)->available; + } + + size_t + BlockStorage::room(Handle* h) { + return byte_address(storage_end(h)) - block_header(h)->available; + } + + Pointer + BlockStorage::book(Handle* h, size_t n) { + BlockHeader* block = block_header(h); + void* const p = block->available; + block->available += n; + return p; } + // ----------------- // -- FileMapping -- |