fastmalloc.cpp

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

    pagemap_.set(span->start, span);
    if (span->length > 1) {
      pagemap_.set(span->start + span->length - 1, span);
    }
  }
  
    // Allocate a large span of length == n.  If successful, returns a
  // span of exactly the specified length.  Else, returns NULL.
  Span* AllocLarge(Length n);

  // Incrementally release some memory to the system.
  // IncrementalScavenge(n) is called whenever n pages are freed.
  void IncrementalScavenge(Length n);

  // Number of pages to deallocate before doing more scavenging
  int64_t scavenge_counter_;

  // Index of last free list we scavenged
  size_t scavenge_index_;
  
#if defined(WTF_CHANGES) && PLATFORM(DARWIN)
  friend class FastMallocZone;
#endif
};

void TCMalloc_PageHeap::init()
{
  pagemap_.init(MetaDataAlloc);
  pagemap_cache_ = PageMapCache(0);
  free_pages_ = 0;
  system_bytes_ = 0;
  scavenge_counter_ = 0;
  // Start scavenging at kMaxPages list
  scavenge_index_ = kMaxPages-1;
  COMPILE_ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits), valuebits);
  DLL_Init(&large_.normal);
  DLL_Init(&large_.returned);
  for (size_t i = 0; i < kMaxPages; i++) {
    DLL_Init(&free_[i].normal);
    DLL_Init(&free_[i].returned);
  }
}

inline Span* TCMalloc_PageHeap::New(Length n) {
  ASSERT(Check());
  ASSERT(n > 0);

  // Find first size >= n that has a non-empty list
  for (Length s = n; s < kMaxPages; s++) {
    Span* ll = NULL;
    bool released = false;
    if (!DLL_IsEmpty(&free_[s].normal)) {
      // Found normal span
      ll = &free_[s].normal;
    } else if (!DLL_IsEmpty(&free_[s].returned)) {
      // Found returned span; reallocate it
      ll = &free_[s].returned;
      released = true;
    } else {
      // Keep looking in larger classes
      continue;
    }

    Span* result = ll->next;
    Carve(result, n, released);
#if TCMALLOC_TRACK_DECOMMITED_SPANS
    if (result->decommitted) {
        TCMalloc_SystemCommit(reinterpret_cast<void*>(result->start << kPageShift), static_cast<size_t>(n << kPageShift));
        result->decommitted = false;
    }
#endif
    ASSERT(Check());
    free_pages_ -= n;
    return result;
  }

  Span* result = AllocLarge(n);
  if (result != NULL) {
      ASSERT_SPAN_COMMITTED(result);
      return result;
  }

  // Grow the heap and try again
  if (!GrowHeap(n)) {
    ASSERT(Check());
    return NULL;
  }

  return AllocLarge(n);
}

Span* TCMalloc_PageHeap::AllocLarge(Length n) {
  // find the best span (closest to n in size).
  // The following loops implements address-ordered best-fit.
  bool from_released = false;
  Span *best = NULL;

  // Search through normal list
  for (Span* span = large_.normal.next;
       span != &large_.normal;
       span = span->next) {
    if (span->length >= n) {
      if ((best == NULL)
          || (span->length < best->length)
          || ((span->length == best->length) && (span->start < best->start))) {
        best = span;
        from_released = false;
      }
    }
  }

  // Search through released list in case it has a better fit
  for (Span* span = large_.returned.next;
       span != &large_.returned;
       span = span->next) {
    if (span->length >= n) {
      if ((best == NULL)
          || (span->length < best->length)
          || ((span->length == best->length) && (span->start < best->start))) {
        best = span;
        from_released = true;
      }
    }
  }

  if (best != NULL) {
    Carve(best, n, from_released);
#if TCMALLOC_TRACK_DECOMMITED_SPANS
    if (best->decommitted) {
        TCMalloc_SystemCommit(reinterpret_cast<void*>(best->start << kPageShift), static_cast<size_t>(n << kPageShift));
        best->decommitted = false;
    }
#endif
    ASSERT(Check());
    free_pages_ -= n;
    return best;
  }
  return NULL;
}

Span* TCMalloc_PageHeap::Split(Span* span, Length n) {
  ASSERT(0 < n);
  ASSERT(n < span->length);
  ASSERT(!span->free);
  ASSERT(span->sizeclass == 0);
  Event(span, 'T', n);

  const Length extra = span->length - n;
  Span* leftover = NewSpan(span->start + n, extra);
  Event(leftover, 'U', extra);
  RecordSpan(leftover);
  pagemap_.set(span->start + n - 1, span); // Update map from pageid to span
  span->length = n;

  return leftover;
}

#if !TCMALLOC_TRACK_DECOMMITED_SPANS
static ALWAYS_INLINE void propagateDecommittedState(Span*, Span*) { }
#else
static ALWAYS_INLINE void propagateDecommittedState(Span* destination, Span* source)
{
    destination->decommitted = source->decommitted;
}
#endif

inline void TCMalloc_PageHeap::Carve(Span* span, Length n, bool released) {
  ASSERT(n > 0);
  DLL_Remove(span);
  span->free = 0;
  Event(span, 'A', n);

  const int extra = static_cast<int>(span->length - n);
  ASSERT(extra >= 0);
  if (extra > 0) {
    Span* leftover = NewSpan(span->start + n, extra);
    leftover->free = 1;
    propagateDecommittedState(leftover, span);
    Event(leftover, 'S', extra);
    RecordSpan(leftover);

    // Place leftover span on appropriate free list
    SpanList* listpair = (static_cast<size_t>(extra) < kMaxPages) ? &free_[extra] : &large_;
    Span* dst = released ? &listpair->returned : &listpair->normal;
    DLL_Prepend(dst, leftover);

    span->length = n;
    pagemap_.set(span->start + n - 1, span);
  }
}

#if !TCMALLOC_TRACK_DECOMMITED_SPANS
static ALWAYS_INLINE void mergeDecommittedStates(Span*, Span*) { }
#else
static ALWAYS_INLINE void mergeDecommittedStates(Span* destination, Span* other)
{
    if (other->decommitted)
        destination->decommitted = true;
}
#endif

inline void TCMalloc_PageHeap::Delete(Span* span) {
  ASSERT(Check());
  ASSERT(!span->free);
  ASSERT(span->length > 0);
  ASSERT(GetDescriptor(span->start) == span);
  ASSERT(GetDescriptor(span->start + span->length - 1) == span);
  span->sizeclass = 0;
#ifndef NO_TCMALLOC_SAMPLES
  span->sample = 0;
#endif

  // Coalesce -- we guarantee that "p" != 0, so no bounds checking
  // necessary.  We do not bother resetting the stale pagemap
  // entries for the pieces we are merging together because we only
  // care about the pagemap entries for the boundaries.
  //
  // Note that the spans we merge into "span" may come out of
  // a "returned" list.  For simplicity, we move these into the
  // "normal" list of the appropriate size class.
  const PageID p = span->start;
  const Length n = span->length;
  Span* prev = GetDescriptor(p-1);
  if (prev != NULL && prev->free) {
    // Merge preceding span into this span
    ASSERT(prev->start + prev->length == p);
    const Length len = prev->length;
    mergeDecommittedStates(span, prev);
    DLL_Remove(prev);
    DeleteSpan(prev);
    span->start -= len;
    span->length += len;
    pagemap_.set(span->start, span);
    Event(span, 'L', len);
  }
  Span* next = GetDescriptor(p+n);
  if (next != NULL && next->free) {
    // Merge next span into this span
    ASSERT(next->start == p+n);
    const Length len = next->length;
    mergeDecommittedStates(span, next);
    DLL_Remove(next);
    DeleteSpan(next);
    span->length += len;
    pagemap_.set(span->start + span->length - 1, span);
    Event(span, 'R', len);
  }

  Event(span, 'D', span->length);
  span->free = 1;
  if (span->length < kMaxPages) {
    DLL_Prepend(&free_[span->length].normal, span);
  } else {
    DLL_Prepend(&large_.normal, span);
  }
  free_pages_ += n;

  IncrementalScavenge(n);
  ASSERT(Check());
}

void TCMalloc_PageHeap::IncrementalScavenge(Length n) {
  // Fast path; not yet time to release memory
  scavenge_counter_ -= n;
  if (scavenge_counter_ >= 0) return;  // Not yet time to scavenge

  // If there is nothing to release, wait for so many pages before
  // scavenging again.  With 4K pages, this comes to 16MB of memory.
  static const size_t kDefaultReleaseDelay = 1 << 8;

  // Find index of free list to scavenge
  size_t index = scavenge_index_ + 1;
  for (size_t i = 0; i < kMaxPages+1; i++) {
    if (index > kMaxPages) index = 0;
    SpanList* slist = (index == kMaxPages) ? &large_ : &free_[index];
    if (!DLL_IsEmpty(&slist->normal)) {
      // Release the last span on the normal portion of this list
      Span* s = slist->normal.prev;
      DLL_Remove(s);
      TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
                             static_cast<size_t>(s->length << kPageShift));
#if TCMALLOC_TRACK_DECOMMITED_SPANS
      s->decommitted = true;
#endif
      DLL_Prepend(&slist->returned, s);

      scavenge_counter_ = std::max<size_t>(64UL, std::min<size_t>(kDefaultReleaseDelay, kDefaultReleaseDelay - (free_pages_ / kDefaultReleaseDelay)));

      if (index == kMaxPages && !DLL_IsEmpty(&slist->normal))
        scavenge_index_ = index - 1;
      else
        scavenge_index_ = index;
      return;
    }
    index++;
  }

  // Nothing to scavenge, delay for a while
  scavenge_counter_ = kDefaultReleaseDelay;
}

void TCMalloc_PageHeap::RegisterSizeClass(Span* span, size_t sc) {
  // Associate span object with all interior pages as well
  ASSERT(!span->free);
  ASSERT(GetDescriptor(span->start) == span);
  ASSERT(GetDescriptor(span->start+span->length-1) == span);
  Event(span, 'C', sc);
  span->sizeclass = static_cast<unsigned int>(sc);
  for (Length i = 1; i < span->length-1; i++) {
    pagemap_.set(span->start+i, span);
  }
}
    
#ifdef WTF_CHANGES
size_t TCMalloc_PageHeap::ReturnedBytes() const {
    size_t result = 0;
    for (unsigned s = 0; s < kMaxPages; s++) {
        const int r_length = DLL_Length(&free_[s].returned);
        unsigned r_pages = s * r_length;
        result += r_pages << kPageShift;
    }
    
    for (Span* s = large_.returned.next; s != &large_.returned; s = s->next)
        result += s->length << kPageShift;
    return result;
}
#endif

#ifndef WTF_CHANGES
static double PagesToMB(uint64_t pages) {
  return (pages << kPageShift) / 1048576.0;
}

void TCMalloc_PageHeap::Dump(TCMalloc_Printer* out) {
  int nonempty_sizes = 0;
  for (int s = 0; s < kMaxPages; s++) {
    if (!DLL_IsEmpty(&free_[s].normal) || !DLL_IsEmpty(&free_[s].returned)) {
      nonempty_sizes++;
    }
  }
  out->printf("------------------------------------------------\n");
  out->printf("PageHeap: %d sizes; %6.1f MB free\n",
              nonempty_sizes, PagesToMB(free_pages_));
  out->printf("------------------------------------------------\n");
  uint64_t total_normal = 0;
  uint64_t total_returned = 0;
  for (int s = 0; s < kMaxPages; s++) {
    const int n_length = DLL_Length(&free_[s].normal);
    const int r_length = DLL_Length(&free_[s].returned);
    if (n_length + r_length > 0) {
      uint64_t n_pages = s * n_length;
      uint64_t r_pages = s * r_length;
      total_normal += n_pages;
      total_returned += r_pages;
      out->printf("%6u pages * %6u spans ~ %6.1f MB; %6.1f MB cum"
                  "; unmapped: %6.1f MB; %6.1f MB cum\n",
                  s,
                  (n_length + r_length),
                  PagesToMB(n_pages + r_pages),
                  PagesToMB(total_normal + total_returned),
                  PagesToMB(r_pages),
                  PagesToMB(total_returned));
    }
  }

  uint64_t n_pages = 0;
  uint64_t r_pages = 0;
  int n_spans = 0;
  int r_spans = 0;
  out->printf("Normal large spans:\n");
  for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) {
    out->printf("   [ %6" PRIuS " pages ] %6.1f MB\n",
                s->length, PagesToMB(s->length));
    n_pages += s->length;
    n_spans++;
  }
  out->printf("Unmapped large spans:\n");
  for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) {
    out->printf("   [ %6" PRIuS " pages ] %6.1f MB\n",
                s->length, PagesToMB(s->length));
    r_pages += s->length;
    r_spans++;
  }
  total_normal += n_pages;
  total_returned += r_pages;
  out->printf(">255   large * %6u spans ~ %6.1f MB; %6.1f MB cum"
              "; unmapped: %6.1f MB; %6.1f MB cum\n",
              (n_spans + r_spans),
              PagesToMB(n_pages + r_pages),
              PagesToMB(total_normal + total_returned),
              PagesToMB(r_pages),
              PagesToMB(total_returned));
}
#endif

bool TCMalloc_PageHeap::GrowHeap(Length n) {
  ASSERT(kMaxPages >= kMinSystemAlloc);
  if (n > kMaxValidPages) return false;
  Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc);
  size_t actual_size;
  void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
  if (ptr == NULL) {
    if (n < ask) {