OLD | NEW |
1 // Copyright (c) 2008, Google Inc. | 1 // Copyright (c) 2008, Google Inc. |
2 // All rights reserved. | 2 // All rights reserved. |
3 // | 3 // |
4 // Redistribution and use in source and binary forms, with or without | 4 // Redistribution and use in source and binary forms, with or without |
5 // modification, are permitted provided that the following conditions are | 5 // modification, are permitted provided that the following conditions are |
6 // met: | 6 // met: |
7 // | 7 // |
8 // * Redistributions of source code must retain the above copyright | 8 // * Redistributions of source code must retain the above copyright |
9 // notice, this list of conditions and the following disclaimer. | 9 // notice, this list of conditions and the following disclaimer. |
10 // * Redistributions in binary form must reproduce the above | 10 // * Redistributions in binary form must reproduce the above |
(...skipping 30 matching lines...) Expand all Loading... |
41 #include "base/spinlock.h" | 41 #include "base/spinlock.h" |
42 #include "base/thread_annotations.h" | 42 #include "base/thread_annotations.h" |
43 #include "common.h" | 43 #include "common.h" |
44 #include "span.h" | 44 #include "span.h" |
45 | 45 |
46 namespace tcmalloc { | 46 namespace tcmalloc { |
47 | 47 |
48 // Data kept per size-class in central cache. | 48 // Data kept per size-class in central cache. |
49 class CentralFreeList { | 49 class CentralFreeList { |
50 public: | 50 public: |
51 // A CentralFreeList may be used before its constructor runs. | |
52 // So we prevent lock_'s constructor from doing anything to the | |
53 // lock_ state. | |
54 CentralFreeList() : lock_(base::LINKER_INITIALIZED) { } | |
55 | |
56 void Init(size_t cl); | 51 void Init(size_t cl); |
57 | 52 |
58 // These methods all do internal locking. | 53 // These methods all do internal locking. |
59 | 54 |
60 // Insert the specified range into the central freelist. N is the number of | 55 // Insert the specified range into the central freelist. N is the number of |
61 // elements in the range. RemoveRange() is the opposite operation. | 56 // elements in the range. RemoveRange() is the opposite operation. |
62 void InsertRange(void *start, void *end, int N); | 57 void InsertRange(void *start, void *end, int N); |
63 | 58 |
64 // Returns the actual number of fetched elements and sets *start and *end. | 59 // Returns the actual number of fetched elements and sets *start and *end. |
65 int RemoveRange(void **start, void **end, int N); | 60 int RemoveRange(void **start, void **end, int N); |
66 | 61 |
67 // Returns the number of free objects in cache. | 62 // Returns the number of free objects in cache. |
68 int length() { | 63 int length() { |
69 SpinLockHolder h(&lock_); | 64 SpinLockHolder h(&lock_); |
70 return counter_; | 65 return counter_; |
71 } | 66 } |
72 | 67 |
73 // Returns the number of free objects in the transfer cache. | 68 // Returns the number of free objects in the transfer cache. |
74 int tc_length(); | 69 int tc_length(); |
75 | 70 |
76 // Returns the memory overhead (internal fragmentation) attributable | |
77 // to the freelist. This is memory lost when the size of elements | |
78 // in a freelist doesn't exactly divide the page-size (an 8192-byte | |
79 // page full of 5-byte objects would have 2 bytes memory overhead). | |
80 size_t OverheadBytes(); | |
81 | |
82 private: | 71 private: |
83 // TransferCache is used to cache transfers of | 72 // TransferCache is used to cache transfers of |
84 // sizemap.num_objects_to_move(size_class) back and forth between | 73 // sizemap.num_objects_to_move(size_class) back and forth between |
85 // thread caches and the central cache for a given size class. | 74 // thread caches and the central cache for a given size class. |
86 struct TCEntry { | 75 struct TCEntry { |
87 void *head; // Head of chain of objects. | 76 void *head; // Head of chain of objects. |
88 void *tail; // Tail of chain of objects. | 77 void *tail; // Tail of chain of objects. |
89 }; | 78 }; |
90 | 79 |
91 // A central cache freelist can have anywhere from 0 to kMaxNumTransferEntries | 80 // A central cache freelist can have anywhere from 0 to kNumTransferEntries |
92 // slots to put link list chains into. | 81 // slots to put link list chains into. To keep memory usage bounded the total |
| 82 // number of TCEntries across size classes is fixed. Currently each size |
| 83 // class is initially given one TCEntry which also means that the maximum any |
| 84 // one class can have is kNumClasses. |
93 #ifdef TCMALLOC_SMALL_BUT_SLOW | 85 #ifdef TCMALLOC_SMALL_BUT_SLOW |
94 // For the small memory model, the transfer cache is not used. | 86 // For the small memory model, the transfer cache is not used. |
95 static const int kMaxNumTransferEntries = 0; | 87 static const int kNumTransferEntries = 0; |
96 #else | 88 #else |
97 // Starting point for the the maximum number of entries in the transfer cache. | 89 static const int kNumTransferEntries = kNumClasses; |
98 // This actual maximum for a given size class may be lower than this | |
99 // maximum value. | |
100 static const int kMaxNumTransferEntries = 64; | |
101 #endif | 90 #endif |
102 | 91 |
103 // REQUIRES: lock_ is held | 92 // REQUIRES: lock_ is held |
104 // Remove object from cache and return. | 93 // Remove object from cache and return. |
105 // Return NULL if no free entries in cache. | 94 // Return NULL if no free entries in cache. |
106 void* FetchFromSpans() EXCLUSIVE_LOCKS_REQUIRED(lock_); | 95 void* FetchFromSpans() EXCLUSIVE_LOCKS_REQUIRED(lock_); |
107 | 96 |
108 // REQUIRES: lock_ is held | 97 // REQUIRES: lock_ is held |
109 // Remove object from cache and return. Fetches | 98 // Remove object from cache and return. Fetches |
110 // from pageheap if cache is empty. Only returns | 99 // from pageheap if cache is empty. Only returns |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
149 bool ShrinkCache(int locked_size_class, bool force) LOCKS_EXCLUDED(lock_); | 138 bool ShrinkCache(int locked_size_class, bool force) LOCKS_EXCLUDED(lock_); |
150 | 139 |
151 // This lock protects all the data members. cached_entries and cache_size_ | 140 // This lock protects all the data members. cached_entries and cache_size_ |
152 // may be looked at without holding the lock. | 141 // may be looked at without holding the lock. |
153 SpinLock lock_; | 142 SpinLock lock_; |
154 | 143 |
155 // We keep linked lists of empty and non-empty spans. | 144 // We keep linked lists of empty and non-empty spans. |
156 size_t size_class_; // My size class | 145 size_t size_class_; // My size class |
157 Span empty_; // Dummy header for list of empty spans | 146 Span empty_; // Dummy header for list of empty spans |
158 Span nonempty_; // Dummy header for list of non-empty spans | 147 Span nonempty_; // Dummy header for list of non-empty spans |
159 size_t num_spans_; // Number of spans in empty_ plus nonempty_ | |
160 size_t counter_; // Number of free objects in cache entry | 148 size_t counter_; // Number of free objects in cache entry |
161 | 149 |
162 // Here we reserve space for TCEntry cache slots. Space is preallocated | 150 // Here we reserve space for TCEntry cache slots. Since one size class can |
163 // for the largest possible number of entries than any one size class may | 151 // end up getting all the TCEntries quota in the system we just preallocate |
164 // accumulate. Not all size classes are allowed to accumulate | 152 // sufficient number of entries here. |
165 // kMaxNumTransferEntries, so there is some wasted space for those size | 153 TCEntry tc_slots_[kNumTransferEntries]; |
166 // classes. | |
167 TCEntry tc_slots_[kMaxNumTransferEntries]; | |
168 | 154 |
169 // Number of currently used cached entries in tc_slots_. This variable is | 155 // Number of currently used cached entries in tc_slots_. This variable is |
170 // updated under a lock but can be read without one. | 156 // updated under a lock but can be read without one. |
171 int32_t used_slots_; | 157 int32_t used_slots_; |
172 // The current number of slots for this size class. This is an | 158 // The current number of slots for this size class. This is an |
173 // adaptive value that is increased if there is lots of traffic | 159 // adaptive value that is increased if there is lots of traffic |
174 // on a given size class. | 160 // on a given size class. |
175 int32_t cache_size_; | 161 int32_t cache_size_; |
176 // Maximum size of the cache for a given size class. | |
177 int32_t max_cache_size_; | |
178 }; | 162 }; |
179 | 163 |
180 // Pads each CentralCache object to multiple of 64 bytes. Since some | 164 // Pads each CentralCache object to multiple of 64 bytes. Since some |
181 // compilers (such as MSVC) don't like it when the padding is 0, I use | 165 // compilers (such as MSVC) don't like it when the padding is 0, I use |
182 // template specialization to remove the padding entirely when | 166 // template specialization to remove the padding entirely when |
183 // sizeof(CentralFreeList) is a multiple of 64. | 167 // sizeof(CentralFreeList) is a multiple of 64. |
184 template<int kFreeListSizeMod64> | 168 template<int kFreeListSizeMod64> |
185 class CentralFreeListPaddedTo : public CentralFreeList { | 169 class CentralFreeListPaddedTo : public CentralFreeList { |
186 private: | 170 private: |
187 char pad_[64 - kFreeListSizeMod64]; | 171 char pad_[64 - kFreeListSizeMod64]; |
188 }; | 172 }; |
189 | 173 |
190 template<> | 174 template<> |
191 class CentralFreeListPaddedTo<0> : public CentralFreeList { | 175 class CentralFreeListPaddedTo<0> : public CentralFreeList { |
192 }; | 176 }; |
193 | 177 |
194 class CentralFreeListPadded : public CentralFreeListPaddedTo< | 178 class CentralFreeListPadded : public CentralFreeListPaddedTo< |
195 sizeof(CentralFreeList) % 64> { | 179 sizeof(CentralFreeList) % 64> { |
196 }; | 180 }; |
197 | 181 |
198 } // namespace tcmalloc | 182 } // namespace tcmalloc |
199 | 183 |
200 #endif // TCMALLOC_CENTRAL_FREELIST_H_ | 184 #endif // TCMALLOC_CENTRAL_FREELIST_H_ |
OLD | NEW |