tcmalloc do_free过程分析

下面我们开始free过程的分析，tcmalloc的free函数主要为tc_free，tc_delete，他们主要调用的还是do_free函数。do_free函数调用do_free_with_callback(ptr, &InvalidFree)并以需要释放的指针和InvalidFree函数指针为参数。下面具体看一下do_free_with_callback函数。首先判断ptr是否为NULL，然后判断pageheap是否已经初始化，如果上述都没有问题，那么根据ptr将ptr转换为PageID，在根据这个PageID，获取到相应的obj的size。

inline void do_free_with_callback(void* ptr, void (*invalid_free_fn)(void*)) {

  if (ptr == NULL) return;

  ASSERT(Static::pageheap() != NULL);  // Should not call free() before malloc()

  const PageID p = reinterpret_cast(ptr) >> kPageShift;

  Span* span = NULL;

  size_t cl = Static::pageheap()->GetSizeClassIfCached(p);

如果获取的size cl为0那么调用函数GetDescriptor通过PageID获取span。GetDescriptor是通过pageheap的pagemap_获取到span。如果span是非法的，那么调用invalid_free_fn（InvalidFree）。

  if (cl == 0) {

    span = Static::pageheap()->GetDescriptor(p);

    if (!span) {

      // span can be NULL because the pointer passed in is invalid

      // (not something returned by malloc or friends), or because the

      // pointer was allocated with some other allocator besides

      // tcmalloc.  The latter can happen if tcmalloc is linked in via

      // a dynamic library, but is not listed last on the link line.

      // In that case, libraries after it on the link line will

      // allocate with libc malloc, but free with tcmalloc's free.

      (*invalid_free_fn)(ptr);  // Decide how to handle the bad free request

      return; 

    }

如果Span是合法且cl为0，那么的那么通过span的sizecalss获取span的size。然后将size和PageID放入pagemap_cache_。

    cl = span->sizeclass;

    Static::pageheap()->CacheSizeClass(p, cl);

  }

如果cl不为0，即需要释放指针所指代的区域size不为0，那么获取当前thread的ThreadCache。如果heap不为NULL，调用heap的Deallocate函数，将这个obj释放到ThreadCache相应size的list中。如果ThreadCache那么直接从centralcache中释放。通过InsertRange将obj返还给相应的entral_cache freelist。

  if (cl != 0) {

    ASSERT(!Static::pageheap()->GetDescriptor(p)->sample);

    ThreadCache* heap = GetCacheIfPresent();

    if (heap != NULL) {

      heap->Deallocate(ptr, cl);

    } else {

      // Delete directly into central cache

      tcmalloc::SLL_SetNext(ptr, NULL);

      Static::central_cache()[cl].InsertRange(ptr, ptr, 1);

    }

  }

如果span是有效的，但是他的classsize还是为0，那么直接通过pageheap调用Delete 函数将他处理。

 else {

    SpinLockHolder h(Static::pageheap_lock());

    ASSERT(reinterpret_cast(ptr) % kPageSize == 0);

    ASSERT(span != NULL && span->start == p);

    if (span->sample) {

      tcmalloc::DLL_Remove(span);

      Static::stacktrace_allocator()->Delete(

          reinterpret_cast(span->objects));

      span->objects = NULL;

    }

    Static::pageheap()->Delete(span);

  }

}

下面分析一下do_free_with_callback函数中通过ThreadCache的Deallcoate函数。该函数首先根据classsize获取相应的FreeList，然后调整ThreadCache的有效size和设置size的顶部，然后将这个obj放入相应的list。

inline void ThreadCache::Deallocate(void* ptr, size_t cl) {

  FreeList* list = &list_[cl];

  size_ += Static::sizemap()->ByteSizeForClass(cl);

  ssize_t size_headroom = max_size_ - size_ - 1;

  list->Push(ptr);

  ssize_t list_headroom =

      static_cast(list->max_length()) - list->length();

 

  // There are two relatively uncommon things that require further work.

  // In the common case we're done, and in that case we need a single branch

  // because of the bitwise-or trick that follows.

如果当前list的长度大于max_length那么还得做相应的处理,通过调用ListTooLong将num_objects_to_move个obj返还给CenteralCache。如果当前Cache的size超过了max_size那么调用Scavenge。

  if ((list_headroom | size_headroom) < 0) {

    if (list_headroom < 0) {

      ListTooLong(list, cl);

    }

    if (size_ >= max_size_) Scavenge();

  }

}

由于是整个ThreadCache的size超过了max_size_，那么需要对整个freeList进行遍历，找到每个lowwatermark>0的list并将此list里面一半的obj返还给CentralCache。同时还得设置一下list的max_length以防止过多的Scavenge调用。

void ThreadCache::Scavenge() {

  // If the low-water mark for the free list is L, it means we would

  // not have had to allocate anything from the central cache even if

  // we had reduced the free list size by L.  We aim to get closer to

  // that situation by dropping L/2 nodes from the free list.  This

  // may not release much memory, but if so we will call scavenge again

  // pretty soon and the low-water marks will be high on that call.

  //int64 start = CycleClock::Now();

  for (int cl = 0; cl < kNumClasses; cl++) {

    FreeList* list = &list_[cl];

    const int lowmark = list->lowwatermark();

    if (lowmark > 0) {

      const int drop = (lowmark > 1) ? lowmark/2 : 1;

      ReleaseToCentralCache(list, cl, drop);

 

      // Shrink the max length if it isn't used.  Only shrink down to

      // batch_size -- if the thread was active enough to get the max_length

      // above batch_size, it will likely be that active again.  If

      // max_length shinks below batch_size, the thread will have to

      // go through the slow-start behavior again.  The slow-start is useful

      // mainly for threads that stay relatively idle for their entire

      // lifetime.

      const int batch_size = Static::sizemap()->num_objects_to_move(cl);

      if (list->max_length() > batch_size) {

        list->set_max_length(

            max(list->max_length() - batch_size, batch_size));

      }

    }

    list->clear_lowwatermark();

  }

 

  IncreaseCacheLimit();

 

//   int64 finish = CycleClock::Now();

//   CycleTimer ct;

//   MESSAGE("GC: %.0f ns\n", ct.CyclesToUsec(finish-start)*1000.0);

}

Pageheap的Delete函数主要讲Span的sizecalss之类的参数设置好，这里面得注意的是将span->location设置为Span::ON_NORMAL_FREELIST，然后调用MergeIntoFreeList将span放入相应的list里面，MergeIntoFreeList主要对当前span的前后相连span进行判断，判断是否可以合并，如果可以合并，那么合并成一个span并调用PrependToFreeList将Span加入PageHeap的normal队列并调整相应的size。

void PageHeap::Delete(Span* span) {

  ASSERT(Check());

  ASSERT(span->location == Span::IN_USE);

  ASSERT(span->length > 0);

  ASSERT(GetDescriptor(span->start) == span);

  ASSERT(GetDescriptor(span->start + span->length - 1) == span);

  const Length n = span->length;

  span->sizeclass = 0;

  span->sample = 0;

  span->location = Span::ON_NORMAL_FREELIST;

  Event(span, 'D', span->length);

  MergeIntoFreeList(span);  // Coalesces if possible

  IncrementalScavenge(n);

  ASSERT(Check());

}

调整好freelist以后，下面将判断是否需要收索内存通过调用IncrementalScavenge实现。scavenge_counter_的默认值是1M页面。

void 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

 

  const double rate = FLAGS_tcmalloc_release_rate;

  if (rate <= 1e-6) {

    // Tiny release rate means that releasing is disabled.

    scavenge_counter_ = kDefaultReleaseDelay;

    return;

  }

通过调用ReleaseAtLeastNPages释放函数，此函数调用ReleaseLastNormalSpan将Normal队列中的Span转到return队列中。

  Length released_pages = ReleaseAtLeastNPages(1);

 

  if (released_pages == 0) {

    // Nothing to scavenge, delay for a while.

    scavenge_counter_ = kDefaultReleaseDelay;

  } else {

    // Compute how long to wait until we return memory.

    // FLAGS_tcmalloc_release_rate==1 means wait for 1000 pages

    // after releasing one page.

    const double mult = 1000.0 / rate;

    double wait = mult * static_cast(released_pages);

    if (wait > kMaxReleaseDelay) {

      // Avoid overflow and bound to reasonable range.

      wait = kMaxReleaseDelay;

    }

    scavenge_counter_ = static_cast(wait);

  }

}

ReleaseLastNormalSpan函数主要将Pageheap normal list中的span进行淘汰，将span淘汰到return队列中去。淘汰的起点是release_index_所指定的list。ReleaseLastNormalSpan主要从list所指定的span队列中将最后一个Span取出放到normal list中去。

Length PageHeap::ReleaseAtLeastNPages(Length num_pages) {

  Length released_pages = 0;

  Length prev_released_pages = -1;

 

  // Round robin through the lists of free spans, releasing the last

  // span in each list.  Stop after releasing at least num_pages.

  while (released_pages < num_pages) {

    if (released_pages == prev_released_pages) {

      // Last iteration of while loop made no progress.

      break;

    }

    prev_released_pages = released_pages;

 

    for (int i = 0; i < kMaxPages+1 && released_pages < num_pages;

         i++, release_index_++) {

      if (release_index_ > kMaxPages) release_index_ = 0;

      SpanList* slist = (release_index_ == kMaxPages) ?

          &large_ : &free_[release_index_];

      if (!DLL_IsEmpty(&slist->normal)) {

        Length released_len = ReleaseLastNormalSpan(slist);

        released_pages += released_len;

      }

    }

  }

  return released_pages;

}

 

         ReleaseLastNormalSpan会调用TCMalloc_SystemRelease，但是这个函数只是调用madvise(reinterpret_cast(new_start), new_end - new_start,                     MADV_DONTNEED)，madvise函数其实并没有做啥实质性的工作。最重要的还是将location设置为Span::ON_RETURNED_FREELIST，然后将span通过MergeIntoFreeList放入return队列。

Length PageHeap::ReleaseLastNormalSpan(SpanList* slist) {

  Span* s = slist->normal.prev;

  ASSERT(s->location == Span::ON_NORMAL_FREELIST);

  RemoveFromFreeList(s);

  const Length n = s->length;

  TCMalloc_SystemRelease(reinterpret_cast(s->start << kPageShift),

                         static_cast(s->length << kPageShift));

  s->location = Span::ON_RETURNED_FREELIST;

  MergeIntoFreeList(s);  // Coalesces if possible.

  return n;

}