Author: Remi Meier <remi.me...@inf.ethz.ch>
Branch: c8-small-uniform
Changeset: r1384:c8192510bcee
Date: 2014-09-16 12:42 +0200
http://bitbucket.org/pypy/stmgc/changeset/c8192510bcee/
Log: add files from c7 branch
diff --git a/c8/stm/smallmalloc.c b/c8/stm/smallmalloc.c
new file mode 100644
--- /dev/null
+++ b/c8/stm/smallmalloc.c
@@ -0,0 +1,310 @@
+#ifndef _STM_CORE_H_
+# error "must be compiled via stmgc.c"
+#endif
+
+
+#define PAGE_SMSIZE_START END_NURSERY_PAGE
+#define PAGE_SMSIZE_END NB_PAGES
+
+typedef struct {
+ uint8_t sz;
+} fpsz_t;
+
+static fpsz_t full_pages_object_size[PAGE_SMSIZE_END - PAGE_SMSIZE_START];
+/* ^^^ This array contains the size (in number of words) of the objects
+ in the given page, provided it's a "full page of small objects". It
+ is 0 if it's not such a page, if it's fully free, or if it's in
+ small_page_lists. It is not 0 as soon as the page enters the
+ segment's 'small_malloc_data.loc_free' (even if the page is not
+ technically full yet, it will be very soon in this case).
+*/
+
+static fpsz_t *get_fpsz(char *smallpage)
+{
+ uintptr_t pagenum = (((char *)smallpage) - stm_object_pages) / 4096;
+ assert(PAGE_SMSIZE_START <= pagenum && pagenum < PAGE_SMSIZE_END);
+ return &full_pages_object_size[pagenum - PAGE_SMSIZE_START];
+}
+
+
+#ifdef STM_TESTS
+bool (*_stm_smallmalloc_keep)(char *data); /* a hook for tests */
+#endif
+
+static void teardown_smallmalloc(void)
+{
+ memset(small_page_lists, 0, sizeof(small_page_lists));
+ assert(free_uniform_pages == NULL); /* done by the previous line */
+ first_small_uniform_loc = (uintptr_t) -1;
+#ifdef STM_TESTS
+ _stm_smallmalloc_keep = NULL;
+#endif
+ memset(full_pages_object_size, 0, sizeof(full_pages_object_size));
+}
+
+static int gmfp_lock = 0;
+
+static void grab_more_free_pages_for_small_allocations(void)
+{
+ /* Grab GCPAGE_NUM_PAGES pages out of the top addresses. Use the
+ lock of pages.c to prevent any remapping from occurring under our
+ feet.
+ */
+ spinlock_acquire(gmfp_lock);
+
+ if (free_uniform_pages == NULL) {
+
+ uintptr_t decrease_by = GCPAGE_NUM_PAGES * 4096;
+ if (uninitialized_page_stop - uninitialized_page_start < decrease_by)
+ goto out_of_memory;
+
+ uninitialized_page_stop -= decrease_by;
+ first_small_uniform_loc = uninitialized_page_stop - stm_object_pages;
+
+ char *base = stm_object_pages + END_NURSERY_PAGE * 4096UL;
+ if (!_stm_largemalloc_resize_arena(uninitialized_page_stop - base))
+ goto out_of_memory;
+
+ setup_N_pages(uninitialized_page_stop, GCPAGE_NUM_PAGES);
+
+ char *p = uninitialized_page_stop;
+ long i;
+ for (i = 0; i < GCPAGE_NUM_PAGES; i++) {
+ ((struct small_free_loc_s *)p)->nextpage = free_uniform_pages;
+ free_uniform_pages = (struct small_free_loc_s *)p;
+ p += 4096;
+ }
+ }
+
+ spinlock_release(gmfp_lock);
+ return;
+
+ out_of_memory:
+ stm_fatalerror("out of memory!\n"); /* XXX */
+}
+
+static char *_allocate_small_slowpath(uint64_t size)
+{
+ long n = size / 8;
+ struct small_free_loc_s *smallpage;
+ struct small_free_loc_s *TLPREFIX *fl =
+ &STM_PSEGMENT->small_malloc_data.loc_free[n];
+ assert(*fl == NULL);
+
+ retry:
+ /* First try to grab the next page from the global 'small_page_list'
+ */
+ smallpage = small_page_lists[n];
+ if (smallpage != NULL) {
+ if (UNLIKELY(!__sync_bool_compare_and_swap(&small_page_lists[n],
+ smallpage,
+ smallpage->nextpage)))
+ goto retry;
+
+ /* Succeeded: we have a page in 'smallpage' */
+ *fl = smallpage->next;
+ get_fpsz((char *)smallpage)->sz = n;
+ return (char *)smallpage;
+ }
+
+ /* There is no more page waiting for the correct size of objects.
+ Maybe we can pick one from free_uniform_pages.
+ */
+ smallpage = free_uniform_pages;
+ if (smallpage != NULL) {
+ if (UNLIKELY(!__sync_bool_compare_and_swap(&free_uniform_pages,
+ smallpage,
+ smallpage->nextpage)))
+ goto retry;
+
+ /* Succeeded: we have a page in 'smallpage', which is not
+ initialized so far, apart from the 'nextpage' field read
+ above. Initialize it.
+ */
+ struct small_free_loc_s *p, **previous;
+ assert(!(((uintptr_t)smallpage) & 4095));
+ previous = (struct small_free_loc_s **)
+ REAL_ADDRESS(STM_SEGMENT->segment_base, fl);
+
+ /* Initialize all slots from the second one to the last one to
+ contain a chained list */
+ uintptr_t i = size;
+ while (i <= 4096 - size) {
+ p = (struct small_free_loc_s *)(((char *)smallpage) + i);
+ *previous = p;
+ previous = &p->next;
+ i += size;
+ }
+ *previous = NULL;
+
+ /* The first slot is immediately returned */
+ get_fpsz((char *)smallpage)->sz = n;
+ return (char *)smallpage;
+ }
+
+ /* Not a single free page left. Grab some more free pages and retry.
+ */
+ grab_more_free_pages_for_small_allocations();
+ goto retry;
+}
+
+__attribute__((always_inline))
+static inline char *allocate_outside_nursery_small(uint64_t size)
+{
+ OPT_ASSERT((size & 7) == 0);
+ OPT_ASSERT(16 <= size && size <= GC_LAST_SMALL_SIZE);
+
+ struct small_free_loc_s *TLPREFIX *fl =
+ &STM_PSEGMENT->small_malloc_data.loc_free[size / 8];
+
+ struct small_free_loc_s *result = *fl;
+
+ if (UNLIKELY(result == NULL))
+ return _allocate_small_slowpath(size);
+
+ *fl = result->next;
+ return (char *)result;
+}
+
+object_t *_stm_allocate_old_small(ssize_t size_rounded_up)
+{
+ char *p = allocate_outside_nursery_small(size_rounded_up);
+ return (object_t *)(p - stm_object_pages);
+}
+
+/************************************************************/
+
+static inline bool _smallmalloc_sweep_keep(char *p)
+{
+#ifdef STM_TESTS
+ if (_stm_smallmalloc_keep != NULL)
+ return _stm_smallmalloc_keep(p);
+#endif
+ abort();
+ //return smallmalloc_keep_object_at(p);
+}
+
+void check_order_inside_small_page(struct small_free_loc_s *page)
+{
+#ifndef NDEBUG
+ /* the free locations are supposed to be in increasing order */
+ while (page->next != NULL) {
+ assert(page->next > page);
+ page = page->next;
+ }
+#endif
+}
+
+static char *getbaseptr(struct small_free_loc_s *fl)
+{
+ return (char *)(((uintptr_t)fl) & ~4095);
+}
+
+void sweep_small_page(char *baseptr, struct small_free_loc_s *page_free,
+ long szword)
+{
+ if (page_free != NULL)
+ check_order_inside_small_page(page_free);
+
+ /* for every non-free location, ask if we must free it */
+ uintptr_t i, size = szword * 8;
+ bool any_object_remaining = false, any_object_dying = false;
+ struct small_free_loc_s *fl = page_free;
+ struct small_free_loc_s *flprev = NULL;
+
+ /* XXX could optimize for the case where all objects die: we don't
+ need to painfully rebuild the free list in the whole page, just
+ to have it ignored in the end because we put the page into
+ 'free_uniform_pages' */
+
+ for (i = 0; i <= 4096 - size; i += size) {
+ char *p = baseptr + i;
+ if (p == (char *)fl) {
+ /* location is already free */
+ flprev = fl;
+ fl = fl->next;
+ any_object_dying = true;
+ }
+ else if (!_smallmalloc_sweep_keep(p)) {
+ /* the location should be freed now */
+ if (flprev == NULL) {
+ flprev = (struct small_free_loc_s *)p;
+ flprev->next = fl;
+ page_free = flprev;
+ }
+ else {
+ assert(flprev->next == fl);
+ flprev->next = (struct small_free_loc_s *)p;
+ flprev = (struct small_free_loc_s *)p;
+ flprev->next = fl;
+ }
+ any_object_dying = true;
+ }
+ else {
+ any_object_remaining = true;
+ }
+ }
+ if (!any_object_remaining) {
+ ((struct small_free_loc_s *)baseptr)->nextpage = free_uniform_pages;
+ free_uniform_pages = (struct small_free_loc_s *)baseptr;
+ }
+ else if (!any_object_dying) {
+ get_fpsz(baseptr)->sz = szword;
+ }
+ else {
+ check_order_inside_small_page(page_free);
+ page_free->nextpage = small_page_lists[szword];
+ small_page_lists[szword] = page_free;
+ }
+}
+
+void _stm_smallmalloc_sweep(void)
+{
+ long i, szword;
+ for (szword = 2; szword < GC_N_SMALL_REQUESTS; szword++) {
+ struct small_free_loc_s *page = small_page_lists[szword];
+ struct small_free_loc_s *nextpage;
+ small_page_lists[szword] = NULL;
+
+ /* process the pages that the various segments are busy filling */
+ for (i = 1; i <= NB_SEGMENTS; i++) {
+ struct stm_priv_segment_info_s *pseg = get_priv_segment(i);
+ struct small_free_loc_s **fl =
+ &pseg->small_malloc_data.loc_free[szword];
+ if (*fl != NULL) {
+ /* the entry in full_pages_object_size[] should already be
+ szword. We reset it to 0. */
+ fpsz_t *fpsz = get_fpsz((char *)*fl);
+ assert(fpsz->sz == szword);
+ fpsz->sz = 0;
+ sweep_small_page(getbaseptr(*fl), *fl, szword);
+ *fl = NULL;
+ }
+ }
+
+ /* process all the other partially-filled pages */
+ while (page != NULL) {
+ /* for every page in small_page_lists: assert that the
+ corresponding full_pages_object_size[] entry is 0 */
+ assert(get_fpsz((char *)page)->sz == 0);
+ nextpage = page->nextpage;
+ sweep_small_page(getbaseptr(page), page, szword);
+ page = nextpage;
+ }
+ }
+
+ /* process the really full pages, which are the ones which still
+ have a non-zero full_pages_object_size[] entry */
+ char *pageptr = uninitialized_page_stop;
+ fpsz_t *fpsz_start = get_fpsz(pageptr);
+ fpsz_t *fpsz_end = &full_pages_object_size[PAGE_SMSIZE_END -
+ PAGE_SMSIZE_START];
+ fpsz_t *fpsz;
+ for (fpsz = fpsz_start; fpsz < fpsz_end; fpsz++, pageptr += 4096) {
+ uint8_t sz = fpsz->sz;
+ if (sz != 0) {
+ fpsz->sz = 0;
+ sweep_small_page(pageptr, NULL, sz);
+ }
+ }
+}
diff --git a/c8/stm/smallmalloc.h b/c8/stm/smallmalloc.h
new file mode 100644
--- /dev/null
+++ b/c8/stm/smallmalloc.h
@@ -0,0 +1,66 @@
+
+/* Outside the nursery, we are taking from the highest addresses
+ complete pages, one at a time, which uniformly contain objects of
+ size "8 * N" for some N in range(2, GC_N_SMALL_REQUESTS). We are
+ taking from the lowest addresses "large" objects, which are at least
+ 288 bytes long, allocated by largemalloc.c. The limit is the same
+ as used in PyPy's default GC.
+*/
+
+#define GC_N_SMALL_REQUESTS 36
+#define GC_LAST_SMALL_SIZE (8 * (GC_N_SMALL_REQUESTS - 1))
+
+
+struct small_free_loc_s {
+ /* A chained list of locations within the same page which are
+ free. */
+ struct small_free_loc_s *next;
+
+ /* A chained list of all small pages containing objects of a given
+ small size, and that have at least one free object. It points
+ *inside* the next page, to another struct small_free_loc_s. This
+ field is only meaningful on the first small_free_loc_s of a given
+ page! */
+ struct small_free_loc_s *nextpage;
+
+ /* This structure is only two words, so it always fits inside one
+ free slot inside the page. */
+};
+
+
+/* For every size from 16 bytes to 8*(GC_N_SMALL_REQUESTS-1), this is
+ a list of pages that contain objects of that size and have at least
+ one free location. Additionally, the item 0 in the following list
+ is a chained list of fully-free pages (which can be reused for a
+ different size than the one they originally contained).
+*/
+static struct small_free_loc_s *small_page_lists[GC_N_SMALL_REQUESTS];
+
+#define free_uniform_pages (small_page_lists[0])
+
+
+/* For is_small_uniform(). */
+static uintptr_t first_small_uniform_loc = (uintptr_t) -1;
+
+
+/* This is a definition for 'STM_PSEGMENT->small_malloc_data'. Each
+ segment grabs one page at a time from the global list, and then
+ requests for data are answered locally.
+*/
+struct small_malloc_data_s {
+ struct small_free_loc_s *loc_free[GC_N_SMALL_REQUESTS];
+};
+
+
+/* Functions
+ */
+static inline char *allocate_outside_nursery_small(uint64_t size)
+ __attribute__((always_inline));
+
+void _stm_smallmalloc_sweep(void);
+
+static void teardown_smallmalloc(void);
+
+static inline bool is_small_uniform(object_t *obj) {
+ return ((uintptr_t)obj) >= first_small_uniform_loc;
+}
diff --git a/c8/test/test_smallmalloc.py b/c8/test/test_smallmalloc.py
new file mode 100644
--- /dev/null
+++ b/c8/test/test_smallmalloc.py
@@ -0,0 +1,76 @@
+from support import *
+import random
+
+
+def pageof(p):
+ return int(ffi.cast("uintptr_t", p)) >> 12
+
+
+class TestSmallMalloc(BaseTest):
+
+ def setup_method(self, method):
+ BaseTest.setup_method(self, method)
+ @ffi.callback("bool(char *)")
+ def keep(data):
+ p = ffi.cast("object_t *", data - lib.stm_object_pages)
+ self.has_been_asked_for.append(p)
+ return p in self.keep_me
+ lib._stm_smallmalloc_keep = keep
+ self._keepalive_keep_function = keep
+ self.keep_me = set()
+ self.has_been_asked_for = []
+
+ def test_simple_uniform(self):
+ page0 = [stm_allocate_old_small(16) for i in range(0, 4096, 16)]
+ assert len(set(map(pageof, page0))) == 1
+ #
+ page1 = [stm_allocate_old_small(16) for i in range(0, 4096, 16)]
+ assert len(set(map(pageof, page1))) == 1
+ #
+ assert len(set(map(pageof, page0 + page1))) == 2
+
+ def test_different_sizes_different_pages(self):
+ seen = []
+ for i in range(2, GC_N_SMALL_REQUESTS):
+ p = pageof(stm_allocate_old_small(8 * i))
+ assert p not in seen
+ seen.append(p)
+ for i in range(2, GC_N_SMALL_REQUESTS):
+ p = pageof(stm_allocate_old_small(8 * i))
+ assert p == seen[0]
+ seen.pop(0)
+
+ def test_sweep_freeing_simple(self):
+ p1 = stm_allocate_old_small(16)
+ lib._stm_smallmalloc_sweep()
+
+ def test_sweep_freeing_random_subset(self):
+ for i in range(50):
+ page0 = [stm_allocate_old_small(16) for i in range(0, 4096, 16)]
+ assert len(set(map(pageof, page0))) == 1
+ tid = lib._get_type_id(page0[0])
+ while len(page0) > 0:
+ self.keep_me = set(random.sample(page0, len(page0) // 2))
+ self.has_been_asked_for = []
+ lib._stm_smallmalloc_sweep()
+ assert sorted(page0) == self.has_been_asked_for
+ page0r = []
+ for p in page0:
+ if p in self.keep_me:
+ assert lib._get_type_id(p) == tid
+ page0r.append(p)
+ else:
+ assert lib._get_type_id(p) != tid
+ page0 = page0r
+ if len(page0) > 10:
+ p = stm_allocate_old_small(16)
+ assert pageof(p) == pageof(page0[0])
+ page0.append(p)
+
+ def test_sweep_full_page_remains_full(self):
+ page0 = [stm_allocate_old_small(16) for i in range(0, 4096, 16)]
+ tid = lib._get_type_id(page0[0])
+ self.keep_me = set(page0)
+ lib._stm_smallmalloc_sweep()
+ for p in page0:
+ assert lib._get_type_id(p) == tid
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
