|
1 // Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
2 // All rights reserved. |
|
3 // This component and the accompanying materials are made available |
|
4 // under the terms of the License "Eclipse Public License v1.0" |
|
5 // which accompanies this distribution, and is available |
|
6 // at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
7 // |
|
8 // Initial Contributors: |
|
9 // Nokia Corporation - initial contribution. |
|
10 // |
|
11 // Contributors: |
|
12 // |
|
13 // Description: |
|
14 // |
|
15 |
|
16 #include <kernel/kern_priv.h> |
|
17 #include "maddrcont.h" |
|
18 |
|
19 RAddressedContainer::RAddressedContainer(NFastMutex* aReadLock, DMutex*& aWriteLock) |
|
20 : iMaxCount(0), iCount(0), iList(0), iReadLock(aReadLock), iWriteLock(aWriteLock) |
|
21 {} |
|
22 |
|
23 |
|
24 RAddressedContainer::~RAddressedContainer() |
|
25 { |
|
26 Kern::Free(iList); |
|
27 } |
|
28 |
|
29 |
|
30 const TUint MinCount = 8; // must be power of two |
|
31 |
|
32 FORCE_INLINE TUint RAddressedContainer::CalculateGrow() |
|
33 { |
|
34 TUint newMax = iMaxCount; |
|
35 |
|
36 if(newMax<MinCount) |
|
37 newMax = MinCount; |
|
38 else |
|
39 newMax <<= 1; |
|
40 return newMax; |
|
41 } |
|
42 |
|
43 |
|
44 TUint RAddressedContainer::CalculateShrink(TUint aCount) |
|
45 { |
|
46 TUint newMax = iMaxCount; |
|
47 if(!aCount) |
|
48 return 0; // empty container should have zero max size |
|
49 |
|
50 #ifndef _DEBUG |
|
51 // we want at least 'MinCount' free slots after shrinking for hysteresis, |
|
52 // but not in UDEB builds because OOM testing will barf... |
|
53 aCount += MinCount; |
|
54 #endif |
|
55 |
|
56 TUint tryMax = newMax; |
|
57 do |
|
58 { |
|
59 newMax = tryMax; |
|
60 tryMax >>= 1; |
|
61 } |
|
62 while(tryMax>=aCount); |
|
63 |
|
64 if(newMax<MinCount) |
|
65 newMax = MinCount; |
|
66 |
|
67 return newMax; |
|
68 } |
|
69 |
|
70 |
|
71 TBool RAddressedContainer::CheckWriteLock() |
|
72 { |
|
73 if(K::Initialising) |
|
74 return true; // check disabled during boot as we are single threaded at that point |
|
75 if(!iWriteLock) |
|
76 return false; |
|
77 if((((TLinAddr)iWriteLock)&1)) |
|
78 return true; // its a lock from DMutexPool, we can't check that, assume it's OK |
|
79 return iWriteLock->iCleanup.iThread==&Kern::CurrentThread(); |
|
80 } |
|
81 |
|
82 |
|
83 #ifdef _DEBUG |
|
84 const TUint KMaxEntriesInOneGo = 4; // small number to improve test coverage |
|
85 #else |
|
86 const TUint KMaxEntriesInOneGo = 32; // to produce a similar worst case number of cache line accesses to the binary search |
|
87 #endif |
|
88 |
|
89 TInt RAddressedContainer::Add(TLinAddr aAddress, TAny* aObject) |
|
90 { |
|
91 __NK_ASSERT_DEBUG(aObject); |
|
92 __ASSERT_CRITICAL; |
|
93 __NK_ASSERT_DEBUG(CheckWriteLock()); |
|
94 |
|
95 #ifdef _DEBUG |
|
96 if(K::CheckForSimulatedAllocFail()) |
|
97 { |
|
98 __KTRACE_OPT(KMMU,Kern::Printf("RAddressedContainer::Add returns simulated OOM %d",KErrNoMemory)); |
|
99 return KErrNoMemory; |
|
100 } |
|
101 #endif |
|
102 |
|
103 // find list insertion point... |
|
104 TUint i = FindIndex(aAddress); |
|
105 |
|
106 if(iCount<iMaxCount) |
|
107 { |
|
108 // insert new entry... |
|
109 ReadLock(); |
|
110 |
|
111 // make room by shuffling entries up in the array KMaxEntriesInOneGo at a time... |
|
112 TEntry* entry = iList+i; |
|
113 TEntry* prev = iList+iCount; |
|
114 ++iCount; // must do this before releasing read lock for the first time |
|
115 for(;;) |
|
116 { |
|
117 TEntry* next = prev-KMaxEntriesInOneGo; |
|
118 if(next<=entry) |
|
119 { |
|
120 // move the final remaining entries... |
|
121 wordmove(entry+1,entry,(TUintPtr)prev-(TUintPtr)entry); |
|
122 break; |
|
123 } |
|
124 wordmove(next+1,next,(TUintPtr)prev-(TUintPtr)next); |
|
125 prev = next; |
|
126 // flash the read lock to give readers a chance to look at the list... |
|
127 ReadFlash(); |
|
128 // Note, readers may see a duplicate entry in the list at 'prev' but this |
|
129 // is OK as the Find functions will still work. |
|
130 } |
|
131 |
|
132 // copy in new entry... |
|
133 entry->iAddress = aAddress; |
|
134 entry->iObject = aObject; |
|
135 |
|
136 ReadUnlock(); |
|
137 } |
|
138 else |
|
139 { |
|
140 // list memory needs expanding... |
|
141 TUint newMaxCount = CalculateGrow(); |
|
142 |
|
143 // allocate new memory... |
|
144 TEntry* newList = (TEntry*)Kern::Alloc(sizeof(TEntry)*newMaxCount); |
|
145 if(!newList) |
|
146 return KErrNoMemory; |
|
147 #ifdef _DEBUG |
|
148 if(iList) |
|
149 K::Allocator->DebugFunction(RAllocator::ECopyDebugInfo, iList, newList); |
|
150 #endif |
|
151 iMaxCount = newMaxCount; |
|
152 |
|
153 // copy list to new memory, and insert new entry... |
|
154 wordmove(newList,iList,sizeof(TEntry)*i); |
|
155 TEntry* entry = newList+i; |
|
156 entry->iAddress = aAddress; |
|
157 entry->iObject = aObject; |
|
158 wordmove(entry+1,iList+i,sizeof(TEntry)*(iCount-i)); |
|
159 |
|
160 // start using new list... |
|
161 TEntry* oldList = iList; |
|
162 ReadLock(); |
|
163 iList = newList; |
|
164 ++iCount; |
|
165 ReadUnlock(); |
|
166 |
|
167 // free memory used for old list... |
|
168 Kern::Free(oldList); |
|
169 } |
|
170 |
|
171 return KErrNone; |
|
172 } |
|
173 |
|
174 |
|
175 TAny* RAddressedContainer::Remove(TLinAddr aAddress) |
|
176 { |
|
177 __ASSERT_CRITICAL; |
|
178 __NK_ASSERT_DEBUG(CheckWriteLock()); |
|
179 |
|
180 // search for it... |
|
181 TUint i = FindIndex(aAddress); |
|
182 TEntry* entry = iList+i-1; |
|
183 |
|
184 if(!i || entry->iAddress!=aAddress) |
|
185 { |
|
186 // not found... |
|
187 return 0; |
|
188 } |
|
189 --i; // make 'i' the index of entry to remove |
|
190 |
|
191 // get object... |
|
192 TAny* result = entry->iObject; |
|
193 __NK_ASSERT_DEBUG(result); |
|
194 |
|
195 TUint newMaxCount = CalculateShrink(iCount-1); |
|
196 |
|
197 if(newMaxCount>=iMaxCount) |
|
198 { |
|
199 remove_without_resize: |
|
200 // remove old entry... |
|
201 ReadLock(); |
|
202 |
|
203 // shuffling entries down in the array KMaxEntriesInOneGo at a time... |
|
204 TEntry* prev = iList+i+1; |
|
205 TEntry* end = iList+iCount; |
|
206 for(;;) |
|
207 { |
|
208 TEntry* next = prev+KMaxEntriesInOneGo; |
|
209 if(next>=end) |
|
210 { |
|
211 // move the final remaining entries... |
|
212 wordmove(prev-1,prev,(TUintPtr)end-(TUintPtr)prev); |
|
213 break; |
|
214 } |
|
215 wordmove(prev-1,prev,(TUintPtr)next-(TUintPtr)prev); |
|
216 prev = next; |
|
217 // flash the read lock to give readers a chance to look at the list... |
|
218 ReadFlash(); |
|
219 // Note, readers may see a duplicate entry at the end of the list but this |
|
220 // is OK as the Find functions will still work. |
|
221 } |
|
222 |
|
223 --iCount; // must do this after moving all the entries |
|
224 ReadUnlock(); |
|
225 } |
|
226 else |
|
227 { |
|
228 // list memory needs shrinking... |
|
229 |
|
230 // allocate new memory... |
|
231 TEntry* newList = 0; |
|
232 if(newMaxCount) |
|
233 { |
|
234 newList = (TEntry*)Kern::Alloc(sizeof(TEntry)*newMaxCount); |
|
235 if(!newList) |
|
236 goto remove_without_resize; // have no memory to shrink array |
|
237 #ifdef _DEBUG |
|
238 if(iList) |
|
239 K::Allocator->DebugFunction(RAllocator::ECopyDebugInfo, iList, newList); |
|
240 #endif |
|
241 } |
|
242 iMaxCount = newMaxCount; |
|
243 |
|
244 // copy list to new memory, deleting removed entry... |
|
245 wordmove(newList,iList,sizeof(TEntry)*i); |
|
246 wordmove(newList+i,iList+i+1,sizeof(TEntry)*(iCount-i-1)); |
|
247 |
|
248 // start using new list... |
|
249 TEntry* oldList = iList; |
|
250 ReadLock(); |
|
251 iList = newList; |
|
252 --iCount; |
|
253 ReadUnlock(); |
|
254 |
|
255 // free memory used for old list... |
|
256 Kern::Free(oldList); |
|
257 } |
|
258 |
|
259 return result; |
|
260 } |
|
261 |
|
262 |
|
263 TAny* RAddressedContainer::Find(TLinAddr aAddress) |
|
264 { |
|
265 if(iReadLock) |
|
266 __NK_ASSERT_DEBUG(iReadLock->HeldByCurrentThread()); |
|
267 else |
|
268 __NK_ASSERT_DEBUG(CheckWriteLock()); |
|
269 |
|
270 TUint i = FindIndex(aAddress); |
|
271 TEntry* entry = iList+i; |
|
272 if(i==0) |
|
273 return 0; |
|
274 --entry; |
|
275 |
|
276 if(aAddress!=entry->iAddress) |
|
277 return 0; |
|
278 |
|
279 TAny* result = entry->iObject; |
|
280 __NK_ASSERT_DEBUG(result); |
|
281 return result; |
|
282 } |
|
283 |
|
284 |
|
285 TAny* RAddressedContainer::Find(TLinAddr aAddress, TUint& aOffset) |
|
286 { |
|
287 if(iReadLock) |
|
288 __NK_ASSERT_DEBUG(iReadLock->HeldByCurrentThread()); |
|
289 else |
|
290 __NK_ASSERT_DEBUG(CheckWriteLock()); |
|
291 |
|
292 TUint i = FindIndex(aAddress); |
|
293 TEntry* entry = iList+i; |
|
294 if(i==0) |
|
295 return 0; |
|
296 --entry; |
|
297 |
|
298 aOffset = aAddress-entry->iAddress; |
|
299 |
|
300 TAny* result = entry->iObject; |
|
301 __NK_ASSERT_DEBUG(result); |
|
302 return result; |
|
303 } |
|
304 |
|
305 |
|
306 TUint RAddressedContainer::FindIndex(TLinAddr aAddress) |
|
307 { |
|
308 TEntry* list = iList; |
|
309 #if 0 |
|
310 // linear search from end... |
|
311 TUint count = iCount; |
|
312 while(count) |
|
313 { |
|
314 if(list[count-1].iAddress<=aAddress) |
|
315 break; |
|
316 --count; |
|
317 } |
|
318 return count; |
|
319 #else |
|
320 // binary search... |
|
321 TUint l = 0; |
|
322 TUint r = iCount; |
|
323 TUint m; |
|
324 while(l<r) |
|
325 { |
|
326 m = (l+r)>>1; |
|
327 TUint32 x = list[m].iAddress; |
|
328 if(x<=aAddress) |
|
329 l = m+1; |
|
330 else |
|
331 r = m; |
|
332 } |
|
333 return r; |
|
334 #endif |
|
335 } |
|
336 |
|
337 |