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