aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authordos-reis <gdr@axiomatics.org>2011-03-17 10:02:54 +0000
committerdos-reis <gdr@axiomatics.org>2011-03-17 10:02:54 +0000
commita101ddeb749d481e984a843de98e560e88af4c96 (patch)
treeb52831c204c4afd44c5114147091b07ed042dd28
parenta03bd87ff6b1273cf95f3ae5158d274672b89e21 (diff)
downloadopen-axiom-a101ddeb749d481e984a843de98e560e88af4c96.tar.gz
* utils/storage.H: Rework.
* utils/storage.cc: Likewise.
-rw-r--r--src/ChangeLog5
-rw-r--r--src/utils/Makefile.in2
-rw-r--r--src/utils/storage.H197
-rw-r--r--src/utils/storage.cc129
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 --