Lines Matching refs:span
606 // For all span-lengths < kMaxPages we keep an exact-size list.
1064 // Information kept for a span (a contiguous run of pages).
1067 Length length; // Number of pages in span
1071 unsigned int free : 1; // Is the span free
1081 // For debugging, we can keep a log events per span
1088 #define ASSERT_SPAN_COMMITTED(span) ASSERT(!span->decommitted)
1091 void Event(Span* span, char op, int v = 0) {
1092 span->history[span->nexthistory] = op;
1093 span->value[span->nexthistory] = v;
1094 span->nexthistory++;
1095 if (span->nexthistory == sizeof(span->history)) span->nexthistory = 0;
1114 static inline void DeleteSpan(Span* span) {
1117 memset(span, 0x3f, sizeof(*span));
1119 span_allocator.Delete(span);
1131 static inline void DLL_Remove(Span* span) {
1132 span->prev->next = span->next;
1133 span->next->prev = span->prev;
1134 span->prev = NULL;
1135 span->next = NULL;
1160 static inline void DLL_Prepend(Span* list, Span* span) {
1161 ASSERT(span->next == NULL);
1162 ASSERT(span->prev == NULL);
1163 span->next = list->next;
1164 span->prev = list;
1165 list->next->prev = span;
1166 list->next = span;
1231 // contiguous runs of pages (called a "span").
1267 // Delete the span "[p, p+n-1]".
1268 // REQUIRES: span was returned by earlier call to New() and
1270 void Delete(Span* span);
1272 // Mark an allocated span as being used for small objects of the
1274 // REQUIRES: span was returned by an earlier call to New()
1276 void RegisterSizeClass(Span* span, size_t sc);
1278 // Split an allocated span into two spans: one of length "n" pages
1279 // followed by another span of length "span->length - n" pages.
1280 // Modifies "*span" to point to the first span of length "n" pages.
1281 // Returns a pointer to the second span.
1283 // REQUIRES: "0 < n < span->length"
1284 // REQUIRES: !span->free
1285 // REQUIRES: span->sizeclass == 0
1286 Span* Split(Span* span, Length n);
1350 // Array mapping from span length to a doubly linked list of free spans
1369 // REQUIRES span->length >= n
1370 // Remove span from its free list, and move any leftover part of
1371 // span into appropriate free lists. Also update "span" to have
1375 // "released" is true iff "span" was found on a "returned" list.
1376 void Carve(Span* span, Length n, bool released);
1378 void RecordSpan(Span* span) {
1379 pagemap_.set(span->start, span);
1380 if (span->length > 1) {
1381 pagemap_.set(span->start + span->length - 1, span);
1385 // Allocate a large span of length == n. If successful, returns a
1386 // span of exactly the specified length. Else, returns NULL.
1522 // Release the last span on the normal portion of this list
1561 // Found normal span
1564 // Found returned span; reallocate it
1583 // The newly allocated memory is from a span that's in the normal span list (already committed). Update the
1610 // find the best span (closest to n in size).
1616 for (Span* span = large_.normal.next;
1617 span != &large_.normal;
1618 span = span->next) {
1619 if (span->length >= n) {
1621 || (span->length < best->length)
1622 || ((span->length == best->length) && (span->start < best->start))) {
1623 best = span;
1630 for (Span* span = large_.returned.next;
1631 span != &large_.returned;
1632 span = span->next) {
1633 if (span->length >= n) {
1635 || (span->length < best->length)
1636 || ((span->length == best->length) && (span->start < best->start))) {
1637 best = span;
1654 // The newly allocated memory is from a span that's in the normal span list (already committed). Update the
1667 Span* TCMalloc_PageHeap::Split(Span* span, Length n) {
1669 ASSERT(n < span->length);
1670 ASSERT(!span->free);
1671 ASSERT(span->sizeclass == 0);
1672 Event(span, 'T', n);
1674 const Length extra = span->length - n;
1675 Span* leftover = NewSpan(span->start + n, extra);
1678 pagemap_.set(span->start + n - 1, span); // Update map from pageid to span
1679 span->length = n;
1689 inline void TCMalloc_PageHeap::Carve(Span* span, Length n, bool released) {
1691 DLL_Remove(span);
1692 span->free = 0;
1693 Event(span, 'A', n);
1695 const int extra = static_cast<int>(span->length - n);
1698 Span* leftover = NewSpan(span->start + n, extra);
1700 propagateDecommittedState(leftover, span);
1704 // Place leftover span on appropriate free list
1709 span->length = n;
1710 pagemap_.set(span->start + n - 1, span);
1726 inline void TCMalloc_PageHeap::Delete(Span* span) {
1728 ASSERT(!span->free);
1729 ASSERT(span->length > 0);
1730 ASSERT(GetDescriptor(span->start) == span);
1731 ASSERT(GetDescriptor(span->start + span->length - 1) == span);
1732 span->sizeclass = 0;
1734 span->sample = 0;
1745 const PageID p = span->start;
1746 const Length n = span->length;
1749 // Merge preceding span into this span
1756 mergeDecommittedStates(span, prev);
1759 span->start -= len;
1760 span->length += len;
1761 pagemap_.set(span->start, span);
1762 Event(span, 'L', len);
1766 // Merge next span into this span
1773 mergeDecommittedStates(span, next);
1776 span->length += len;
1777 pagemap_.set(span->start + span->length - 1, span);
1778 Event(span, 'R', len);
1781 Event(span, 'D', span->length);
1782 span->free = 1;
1783 if (span->decommitted) {
1784 if (span->length < kMaxPages)
1785 DLL_Prepend(&free_[span->length].returned, span);
1787 DLL_Prepend(&large_.returned, span);
1789 if (span->length < kMaxPages)
1790 DLL_Prepend(&free_[span->length].normal, span);
1792 DLL_Prepend(&large_.normal, span);
1797 if (span->decommitted) {
1798 // If the merged span is decommitted, that means we decommitted any neighboring spans that were
1802 // If the merged span remains committed, add the deleted span's size to the free committed pages count.
1831 // Release the last span on the normal portion of this list
1855 void TCMalloc_PageHeap::RegisterSizeClass(Span* span, size_t sc) {
1856 // Associate span object with all interior pages as well
1857 ASSERT(!span->free);
1858 ASSERT(GetDescriptor(span->start) == span);
1859 ASSERT(GetDescriptor(span->start+span->length-1) == span);
1860 Event(span, 'C', sc);
1861 span->sizeclass = static_cast<unsigned int>(sc);
1862 for (Length i = 1; i < span->length-1; i++) {
1863 pagemap_.set(span->start+i, span);
1991 Span* span = NewSpan(p, ask);
1992 RecordSpan(span);
1993 Delete(span);
1998 // TODO: Once we can return memory to the system, return the new span
2226 for (Span* span = &empty_; span && span != &empty_; span = (span->next ? reader(span->next) : 0))
2227 ASSERT(!span->objects);
2235 for (Span* span = reader(remoteSpan); span && remoteSpan != remoteNonempty; remoteSpan = span->next, span = (span->next ? reader(span->next) : 0)) {
2236 for (void* nextObject = span->objects; nextObject; nextObject = *reader(reinterpret_cast<void**>(nextObject)))
2473 Span* span = pageheap->GetDescriptor(p);
2474 ASSERT(span != NULL);
2475 ASSERT(span->refcount > 0);
2477 // If span is empty, move it to non-empty list
2478 if (span->objects == NULL) {
2479 DLL_Remove(span);
2480 DLL_Prepend(&nonempty_, span);
2481 Event(span, 'N', 0);
2488 for (void* p = span->objects; p != NULL; p = *((void**) p)) {
2492 ASSERT(got + span->refcount ==
2493 (span->length<<kPageShift)/ByteSizeForClass(span->sizeclass));
2497 span->refcount--;
2498 if (span->refcount == 0) {
2499 Event(span, '#', 0);
2500 counter_ -= (span->length<<kPageShift) / ByteSizeForClass(span->sizeclass);
2501 DLL_Remove(span);
2507 pageheap->Delete(span);
2511 *(reinterpret_cast<void**>(object)) = span->objects;
2512 span->objects = object;
2650 Span* span = nonempty_.next;
2652 ASSERT(span->objects != NULL);
2653 ASSERT_SPAN_COMMITTED(span);
2654 span->refcount++;
2655 void* result = span->objects;
2656 span->objects = *(reinterpret_cast<void**>(result));
2657 if (span->objects == NULL) {
2659 DLL_Remove(span);
2660 DLL_Prepend(&empty_, span);
2661 Event(span, 'E', 0);
2673 Span* span;
2676 span = pageheap->New(npages);
2677 if (span) pageheap->RegisterSizeClass(span, size_class_);
2679 if (span == NULL) {
2684 ASSERT_SPAN_COMMITTED(span);
2685 ASSERT(span->length == npages);
2688 // about this span, but that seems to be no better in practice.)
2690 pageheap->CacheSizeClass(span->start + i, size_class_);
2695 void** tail = &span->objects;
2696 char* ptr = reinterpret_cast<char*>(span->start << kPageShift);
2709 span->refcount = 0; // No sub-object in use yet
2711 // Add span to list of non-empty spans
2713 DLL_Prepend(&nonempty_, span);
3425 // Allocate span
3426 Span *span = pageheap->New(pages(size == 0 ? 1 : size));
3427 if (span == NULL) {
3435 return span;
3439 span->sample = 1;
3440 span->objects = stack;
3441 DLL_Prepend(&sampled_objects, span);
3443 return span;
3460 static inline void* SpanToMallocResult(Span *span) {
3461 ASSERT_SPAN_COMMITTED(span);
3462 pageheap->CacheSizeClass(span->start, 0);
3464 CheckedMallocResult(reinterpret_cast<void*>(span->start << kPageShift));
3481 Span* span = DoSampledAllocation(size);
3482 if (span != NULL) {
3483 ret = SpanToMallocResult(span);
3490 Span* span = pageheap->New(pages(size));
3491 if (span != NULL) {
3492 ret = SpanToMallocResult(span);
3514 Span* span = NULL;
3518 span = pageheap->GetDescriptor(p);
3519 cl = span->sizeclass;
3537 ASSERT(span != NULL && span->start == p);
3539 if (span->sample) {
3540 DLL_Remove(span);
3541 stacktrace_allocator.Delete(reinterpret_cast<StackTrace*>(span->objects));
3542 span->objects = NULL;
3545 pageheap->Delete(span);
3589 Span* span = pageheap->New(pages(size));
3590 return span == NULL ? NULL : SpanToMallocResult(span);
3595 Span* span = pageheap->New(alloc);
3596 if (span == NULL) return NULL;
3600 while ((((span->start+skip) << kPageShift) & (align - 1)) != 0) {
3605 Span* rest = pageheap->Split(span, skip);
3606 pageheap->Delete(span);
3607 span = rest;
3612 ASSERT(span->length >= needed);
3613 if (span->length > needed) {
3614 Span* trailer = pageheap->Split(span, needed);
3617 return SpanToMallocResult(span);
3847 Span *span = NULL;
3850 span = pageheap->GetDescriptor(p);
3851 cl = span->sizeclass;
3857 ASSERT(span != NULL);
3858 old_size = span->length << kPageShift;
4147 Span* span = m_reader(reinterpret_cast<Span*>(ptr));
4148 if (span->free) {
4149 void* ptr = reinterpret_cast<void*>(span->start << kPageShift);
4151 } else if (span->sizeclass) {
4152 // Walk the free list of the small-object span, keeping track of each object seen
4153 for (void* nextObject = span->objects; nextObject; nextObject = *m_reader(reinterpret_cast<void**>(nextObject)))
4156 return span->length;
4211 // If it's an allocated large object span, mark it as in use
4217 // Mark each allocated small object within the span as in use
4236 Span* span = m_reader(reinterpret_cast<Span*>(ptr));
4237 if (!span->start)
4241 return span->length;
4245 m_coalescedSpans.append(span);
4246 return span->length;
4253 // If the new span is adjacent to the previous span, do nothing for now.
4254 vm_address_t spanStartAddress = span->start << kPageShift;
4256 m_coalescedSpans.append(span);
4257 return span->length;
4260 // New span is not adjacent to previous span, so record the spans coalesced so far.
4262 m_coalescedSpans.append(span);
4264 return span->length;