=== modified file 'src/alloc.c' --- src/alloc.c 2011-11-20 03:07:02 +0000 +++ src/alloc.c 2011-12-06 05:06:33 +0000 @@ -21,7 +21,7 @@ #include #include /* For CHAR_BIT. */ #include - +#include /* For roundup. */ #include #ifdef HAVE_PTHREAD @@ -2896,9 +2896,12 @@ Vector Allocation ***********************************************************************/ -/* Singly-linked list of all vectors. */ +#ifndef PAGE_SIZE +#define PAGE_SIZE 4096 +#endif -static struct Lisp_Vector *all_vectors; +#define VECTOR_BLOCK_SIZE (PAGE_SIZE - sizeof (void *)) +#define VECTOR_BLOCK_BYTES (VECTOR_BLOCK_SIZE - 2 * sizeof (void *)) /* Handy constants for vectorlike objects. */ enum @@ -2907,6 +2910,301 @@ word_size = sizeof (Lisp_Object) }; +/* Free lists for all possible block-allocated vectors. */ + +#define VECTOR_FREE_LISTS (VECTOR_BLOCK_BYTES / word_size) + +/* Vector blocks are aligned to page size, so it's easy to + get vector block pointer from the vector pointer. */ + +#define VECTOR_BLOCK(v) (struct vector_block *) \ + ((unsigned long)(v) & ~(PAGE_SIZE - 1)) + +/* When the vector is on a free list, vectorlike_header.SIZE is set to + this special value ORed with vector's memory footprint size. */ + +#define VECTOR_FREE_LIST_SIZE \ + (((EMACS_INT) ~0) & ~(ARRAY_MARK_FLAG | PSEUDOVECTOR_FLAG | (PAGE_SIZE - 1))) + +struct vector_block +{ + unsigned char data[VECTOR_BLOCK_BYTES]; + unsigned char *bump; + struct vector_block *next; +}; + +/* Current vector block. */ + +static struct vector_block *vector_block; + +/* Vector free lists, where NTH item points to a chain + of free vectors of NTH * WORD_SIZE bytes. */ + +static struct Lisp_Vector *vector_free_lists[VECTOR_FREE_LISTS]; + +/* Singly-linked list of large vectors. */ + +static struct Lisp_Vector *large_vectors; + +/* Get a new vector block. */ + +static struct vector_block * +allocate_vector_block (void) +{ + struct vector_block *b; + +#ifdef DOUG_LEA_MALLOC + mallopt (M_MMAP_MAX, 0); +#endif + + /* Although lisp_align_malloc should be used, the default + 1K granularity looks too small for vector allocation. */ + b = memalign (PAGE_SIZE, VECTOR_BLOCK_SIZE); + if (!b) + memory_full (VECTOR_BLOCK_SIZE); + +#ifdef DOUG_LEA_MALLOC + mallopt (M_MMAP_MAX, MMAP_MAX_AREAS); +#endif + + memset (b->data, 0, VECTOR_BLOCK_BYTES); + mem_insert (b->data, b->data + VECTOR_BLOCK_BYTES, MEM_TYPE_VECTORLIKE); + + b->bump = b->data; + b->next = vector_block; + vector_block = b; + return b; +} + +/* Called once to initialize vector allocation. */ + +static void +init_vectors (void) +{ + int i; + + large_vectors = NULL; + vector_block = allocate_vector_block (); + + for (i = 0; i < VECTOR_FREE_LISTS; i++) + vector_free_lists[i] = NULL; +} + +/* Allocate vector from the vector block. */ + +static struct Lisp_Vector * +allocate_vector_from_block (size_t nbytes) +{ + struct Lisp_Vector *vector; + struct vector_block *block; + size_t index, restbytes; + + /* Vector with 0 slots for Lisp_Objects is allowed. */ + eassert (nbytes >= sizeof (struct vectorlike_header) && + nbytes <= VECTOR_BLOCK_BYTES); + eassert (nbytes % word_size == 0); + eassert (vector_block != NULL); + + /* First, try to allocate from a free list + contains vectors of the requested size. */ + index = nbytes / word_size; + if (vector_free_lists[index]) + { + vector = vector_free_lists[index]; + vector_free_lists[index] = vector->header.next.vector; + vector->header.next.nbytes = nbytes; + return vector; + } + + /* Next, check free lists contains larger vectors. */ + for (index = (nbytes + sizeof (struct Lisp_Vector)) / word_size; + index < VECTOR_FREE_LISTS; index++) + if (vector_free_lists[index]) + { + struct Lisp_Vector *rest; + + /* This vector is larger than it was requested. */ + vector = vector_free_lists[index]; + vector_free_lists[index] = vector->header.next.vector; + vector->header.next.nbytes = nbytes; + + /* Excessive bytes are used for the smaller vector, + which should be set on an appropriate free list. */ + restbytes = index * word_size - nbytes; + eassert (restbytes % word_size == 0); + rest = (struct Lisp_Vector *) ((char *) vector + nbytes); + rest->header.size = VECTOR_FREE_LIST_SIZE | restbytes; + index = restbytes / word_size; + eassert (index < VECTOR_FREE_LISTS); + rest->header.next.vector = vector_free_lists[index]; + vector_free_lists[index] = rest; + + return vector; + } + + /* Next, try to allocate from current vector block. */ + restbytes = vector_block->data + VECTOR_BLOCK_BYTES - vector_block->bump; + if (nbytes > restbytes) + { + /* Current block's free space isn't enough... */ + if (restbytes >= sizeof (struct Lisp_Vector)) + { + /* ...but it's enough to allocate smaller vector, + which should be set on an appropriate free list. */ + eassert (restbytes % word_size == 0); + vector = (struct Lisp_Vector *) vector_block->bump; + vector_block->bump += restbytes; + vector->header.size = VECTOR_FREE_LIST_SIZE | restbytes; + index = restbytes / word_size; + eassert (index < VECTOR_FREE_LISTS); + vector->header.next.vector = vector_free_lists[index]; + vector_free_lists[index] = vector; + } + /* Anyway, need a new vector block. */ + block = allocate_vector_block (); + } + else + /* Allocate from current vector block. */ + block = vector_block; + + /* Bump pointer allocation from current vector block. */ + vector = (struct Lisp_Vector *) block->bump; + block->bump += nbytes; + vector->header.next.nbytes = nbytes; + return vector; +} + +/* Return amount of Lisp_Objects can be stored in that vector. */ + +#define VECTOR_SIZE(v) ((v)->header.size & PSEUDOVECTOR_FLAG ? \ + (PSEUDOVECTOR_SIZE_MASK & (v)->header.size) : (v)->header.size) + +/* Reclaim space used by unmarked vectors. */ + +static void +sweep_vectors (void) +{ + struct vector_block *block = vector_block, *bprev = NULL, *bnext; + struct Lisp_Vector *vector, *prev, *next; + int index, nr; + + total_vector_size = 0; + for (index = 0; index < VECTOR_FREE_LISTS; index++) + vector_free_lists[index] = NULL; + + /* Looking through vector blocks first. */ + + while (block) + { + struct Lisp_Vector *freearray + [VECTOR_BLOCK_BYTES / sizeof (struct Lisp_Vector)]; + + index = nr = 0; + vector = (struct Lisp_Vector *) block->data; + while ((unsigned char *) vector < block->bump) + { + if ((vector->header.size & VECTOR_FREE_LIST_SIZE) == + VECTOR_FREE_LIST_SIZE) + { + /* This vector is on a free list already. */ + freearray[index++] = vector; + vector->header.next.nbytes = + vector->header.size & (PAGE_SIZE - 1); + } + else + { + if (VECTOR_MARKED_P (vector)) + { + VECTOR_UNMARK (vector), nr++; + total_vector_size += VECTOR_SIZE (vector); + } + else + { + /* This vector is not marked, and it's not on a free list. */ + freearray[index++] = vector; + vector->header.size = + VECTOR_FREE_LIST_SIZE | vector->header.next.nbytes; + } + } + eassert (index < sizeof (freearray) / sizeof (freearray[0])); + eassert (vector->header.next.nbytes != 0); + vector = (struct Lisp_Vector *) + ((unsigned char *) vector + vector->header.next.nbytes); + } + + if (nr) + { + /* This block has some used vectors, which are unmarked. Unused + vectors are collected in FREEARRAY. Setup them on a free lists, + coalescing adjacent free vectors if possible. */ + int i, j; + EMACS_INT nbytes; + + for (i = 0; i < index; i = j) + { + vector = freearray[i]; + nbytes = vector->header.next.nbytes; + + /* Try to form the largest possible free vector. */ + for (j = i + 1; j < index; j++) + { + next = freearray[j]; + if ((struct Lisp_Vector *) + ((unsigned char *) vector + nbytes) == next) + nbytes += next->header.next.nbytes; + else + break; + } + vector->header.next.nbytes = nbytes; + + /* Setup resulting vector on a free list. */ + eassert (vector->header.next.nbytes % word_size == 0); + nr = vector->header.next.nbytes / word_size; + eassert (nr < VECTOR_FREE_LISTS); + vector->header.size = + VECTOR_FREE_LIST_SIZE | vector->header.next.nbytes; + vector->header.next.vector = vector_free_lists[nr]; + vector_free_lists[nr] = vector; + } + bprev = block, block = block->next; + } + else + { + /* This block is no longer used. */ + if (bprev) + bprev->next = block->next; + else + vector_block = block->next; + bnext = block->next; + mem_delete (mem_find (block->data)); + free (block); + block = bnext; + } + } + + /* Next, sweep large vectors. */ + + vector = large_vectors, prev = NULL; + + while (vector) + if (VECTOR_MARKED_P (vector)) + { + VECTOR_UNMARK (vector); + total_vector_size += VECTOR_SIZE (vector); + prev = vector, vector = vector->header.next.vector; + } + else + { + if (prev) + prev->header.next = vector->header.next; + else + large_vectors = vector->header.next.vector; + next = vector->header.next.vector; + lisp_free (vector); + vector = next; + } +} + /* Value is a pointer to a newly allocated Lisp_Vector structure with room for LEN Lisp_Objects. */ @@ -2929,7 +3227,15 @@ /* eassert (!handling_signal); */ nbytes = header_size + len * word_size; - p = (struct Lisp_Vector *) lisp_malloc (nbytes, MEM_TYPE_VECTORLIKE); + if (nbytes > VECTOR_BLOCK_BYTES) + { + p = (struct Lisp_Vector *) lisp_malloc (nbytes, MEM_TYPE_VECTORLIKE); + p->header.next.vector = large_vectors; + large_vectors = p; + } + else + /* Rounding is needed for 32-bit code to preserve 8-byte alignment. */ + p = allocate_vector_from_block (roundup (nbytes, 8)); #ifdef DOUG_LEA_MALLOC /* Back to a reasonable maximum of mmap'ed areas. */ @@ -2939,9 +3245,6 @@ consing_since_gc += nbytes; vector_cells_consed += len; - p->header.next.vector = all_vectors; - all_vectors = p; - MALLOC_UNBLOCK_INPUT; return p; @@ -4016,7 +4319,38 @@ static inline int live_vector_p (struct mem_node *m, void *p) { - return (p == m->start && m->type == MEM_TYPE_VECTORLIKE); + if (m->type == MEM_TYPE_VECTORLIKE) + { + if (m->end - m->start == VECTOR_BLOCK_BYTES) + { + /* This memory node corresponds to a vector block. */ + struct vector_block *block = VECTOR_BLOCK (p); + struct Lisp_Vector *vector = (struct Lisp_Vector *) block->data; + + /* Scan the whole vector block and see whether P points to + the start of some vector which is not on a free list. */ + while ((unsigned char *) vector < block->bump) + { + if ((vector->header.size & VECTOR_FREE_LIST_SIZE) + == VECTOR_FREE_LIST_SIZE) + vector = (struct Lisp_Vector *) + ((unsigned char *) vector + + (vector->header.size & (PAGE_SIZE - 1))); + else if (vector == p) + return 1; + else + vector = (struct Lisp_Vector *) + ((unsigned char *) vector + vector->header.next.nbytes); + } + } + else + { + if (p == m->start) + /* This memory node corresponds to a large vector. */ + return 1; + } + } + return 0; } @@ -6169,33 +6503,7 @@ } } - /* Free all unmarked vectors */ - { - register struct Lisp_Vector *vector = all_vectors, *prev = 0, *next; - total_vector_size = 0; - - while (vector) - if (!VECTOR_MARKED_P (vector)) - { - if (prev) - prev->header.next = vector->header.next; - else - all_vectors = vector->header.next.vector; - next = vector->header.next.vector; - lisp_free (vector); - vector = next; - - } - else - { - VECTOR_UNMARK (vector); - if (vector->header.size & PSEUDOVECTOR_FLAG) - total_vector_size += PSEUDOVECTOR_SIZE_MASK & vector->header.size; - else - total_vector_size += vector->header.size; - prev = vector, vector = vector->header.next.vector; - } - } + sweep_vectors (); #ifdef GC_CHECK_STRING_BYTES if (!noninteractive) @@ -6331,7 +6639,6 @@ Vdead = make_pure_string ("DEAD", 4, 4, 0); #endif - all_vectors = 0; ignore_warnings = 1; #ifdef DOUG_LEA_MALLOC mallopt (M_TRIM_THRESHOLD, 128*1024); /* trim threshold */ @@ -6344,6 +6651,7 @@ init_marker (); init_float (); init_intervals (); + init_vectors (); init_weak_hash_tables (); #ifdef REL_ALLOC === modified file 'src/lisp.h' --- src/lisp.h 2011-12-05 00:15:15 +0000 +++ src/lisp.h 2011-12-06 05:04:46 +0000 @@ -868,12 +868,15 @@ struct vectorlike_header { EMACS_INT size; - - /* Pointer to the next vector-like object. It is generally a buffer or a + /* When the vector is allocated from a vector block, NBYTES is used + if the vector is not on a free list, and VECTOR is used otherwise. + For large vector-like objects, BUFFER or VECTOR is used as a pointer + to the next vector-like object. It is generally a buffer or a Lisp_Vector alias, so for convenience it is a union instead of a pointer: this way, one can write P->next.vector instead of ((struct Lisp_Vector *) P->next). */ union { + EMACS_INT nbytes; struct buffer *buffer; struct Lisp_Vector *vector; } next;