Author: Remi Meier <remi.me...@inf.ethz.ch>
Branch: stmgc-c8
Changeset: r75479:acf538f01489
Date: 2015-01-22 10:59 +0100
http://bitbucket.org/pypy/pypy/changeset/acf538f01489/
Log: add missing files from last commit
diff --git a/rpython/translator/stm/src_stm/stm/smallmalloc.c
b/rpython/translator/stm/src_stm/stm/smallmalloc.c
new file mode 100644
--- /dev/null
+++ b/rpython/translator/stm/src_stm/stm/smallmalloc.c
@@ -0,0 +1,366 @@
+/* Imported by rpython/translator/stm/import_stmgc.py */
+#ifndef _STM_CORE_H_
+# error "must be compiled via stmgc.c"
+#endif
+
+
+#define PAGE_SMSIZE_START 0
+#define PAGE_SMSIZE_END NB_SHARED_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) - END_NURSERY_PAGE * 4096UL -
stm_object_pages) / 4096;
+ /* <= PAGE_SMSIZE_END because we may ask for it when there is no
+ page with smallobjs yet and uninit_page_stop == NB_PAGES... */
+ 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)
+{
+ dprintf(("grab_more_free_pages_for_small_allocation()\n"));
+ /* 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;
+
+ if (!_stm_largemalloc_resize_arena(uninitialized_page_stop -
uninitialized_page_start))
+ goto out_of_memory;
+
+ /* make writable in sharing seg */
+ setup_N_pages(uninitialized_page_stop, GCPAGE_NUM_PAGES);
+
+ char *p = uninitialized_page_stop;
+ long i;
+ for (i = 0; i < GCPAGE_NUM_PAGES; i++) {
+ /* add to free_uniform_pages list */
+ struct small_free_loc_s *to_add = (struct small_free_loc_s *)p;
+
+ retry:
+ to_add->nextpage = free_uniform_pages;
+ if (UNLIKELY(!__sync_bool_compare_and_swap(
+ &free_uniform_pages,
+ to_add->nextpage,
+ to_add))) {
+ goto retry;
+ }
+
+ 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)
+{
+ dprintf(("_allocate_small_slowpath(%lu)\n", 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 stm_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;
+
+ increment_total_allocated(size);
+
+ if (UNLIKELY(result == NULL))
+ return (stm_char*)
+ (_allocate_small_slowpath(size) - stm_object_pages);
+
+ *fl = result->next;
+ dprintf(("allocate_outside_nursery_small(%lu): %p\n",
+ size, (char*)((char *)result - stm_object_pages)));
+ return (stm_char*)
+ ((char *)result - stm_object_pages);
+}
+
+object_t *_stm_allocate_old_small(ssize_t size_rounded_up)
+{
+ stm_char *p = allocate_outside_nursery_small(size_rounded_up);
+ object_t *o = (object_t *)p;
+
+ // sharing seg0 needs to be current:
+ assert(STM_SEGMENT->segment_num == 0);
+ memset(REAL_ADDRESS(STM_SEGMENT->segment_base, o), 0, size_rounded_up);
+ o->stm_flags = GCFLAG_WRITE_BARRIER;
+
+ dprintf(("_stm_allocate_old_small(%lu): %p, seg=%d, page=%lu\n",
+ size_rounded_up, p,
+ get_segment_of_linear_address(stm_object_pages + (uintptr_t)p),
+ (uintptr_t)p / 4096UL));
+
+ return o;
+}
+
+/************************************************************/
+
+static inline bool _smallmalloc_sweep_keep(char *p)
+{
+#ifdef STM_TESTS
+ if (_stm_smallmalloc_keep != NULL) {
+ // test wants a TLPREFIXd address
+ return _stm_smallmalloc_keep((char*)(p - stm_object_pages));
+ }
+#endif
+ 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 */
+ increment_total_allocated(-szword*8);
+#ifdef STM_TESTS
+ /* fill location with 0xdd in all segs except seg0 */
+ int j;
+ object_t *obj = (object_t*)(p - stm_object_pages);
+ uintptr_t page = (baseptr - stm_object_pages) / 4096UL;
+ for (j = 1; j < NB_SEGMENTS; j++)
+ if (get_page_status_in(j, page) == PAGE_ACCESSIBLE)
+ memset(get_virtual_address(j, obj), 0xdd, szword*8);
+#endif
+ //dprintf(("free small %p : %lu\n", (char*)(p - stm_object_pages),
szword*8));
+
+ 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 {
+ //dprintf(("keep small %p : %lu\n", (char*)(p - stm_object_pages),
szword*8));
+ any_object_remaining = true;
+ }
+ }
+ if (!any_object_remaining) {
+ /* give page back to free_uniform_pages and thus make it
+ inaccessible from all other segments again (except seg0) */
+ uintptr_t page = (baseptr - stm_object_pages) / 4096UL;
+ for (i = 1; i < NB_SEGMENTS; i++) {
+ if (get_page_status_in(i, page) == PAGE_ACCESSIBLE)
+ page_mark_inaccessible(i, page);
+ }
+
+ ((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 */
+ /* including sharing seg0 for old-malloced things */
+ for (i = 0; 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/rpython/translator/stm/src_stm/stm/smallmalloc.h
b/rpython/translator/stm/src_stm/stm/smallmalloc.h
new file mode 100644
--- /dev/null
+++ b/rpython/translator/stm/src_stm/stm/smallmalloc.h
@@ -0,0 +1,67 @@
+/* Imported by rpython/translator/stm/import_stmgc.py */
+
+/* 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 stm_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;
+}
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
