1/* 2 * Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24#include "webdavd.h" 25 26#include <stdlib.h> 27#include <pthread.h> 28 29#include "OpaqueIDs.h" 30 31enum 32{ 33 /* 34 * An opaque id is composed of two parts. The lower half is an index into 35 * a table which holds the actual data for the opaque id. The upper half is a 36 * counter which insures that a particular opaque id value isn't reused for a long 37 * time after it has been disposed. Currently, with 20 bits as the index, there 38 * can be (2^20)-2 opaque ids in existence at any particular point in time 39 * (index 0 is not used), and no opaque id value will be re-issued more frequently than every 40 * 2^12th (4096) times. (although, in practice many more opaque ids will be issued 41 * before one is re-used). 42 */ 43 kOpaqueIDIndexBits = 20, 44 kOpaqueIDIndexMask = ((1 << kOpaqueIDIndexBits) - 1), 45 kOpaqueIDMaximumCount = (1 << kOpaqueIDIndexBits) - 1, /* all 0 bits are never a valid index */ 46 47 /* 48 * This keeps a little 'extra room' in the table, so that if it gets 49 * nearly full that a dispose and re-allocate won't quickly run thru the couple 50 * couple free slots in the table. So, if there are less than this number of 51 * available items, the table will get grown. 52 */ 53 kOpaqueIDMinimumFree = 1024, 54 /* When the table is grown, grow by this many entries */ 55 kOpaqueIDGrowCount = 2048 56}; 57 58/* 59 * Create an MPOpaqeID by masking together a count and and index. 60 */ 61#define CreateOpaqueID(counter, index) (opaque_id)(((counter) << kOpaqueIDIndexBits) | ((index) & kOpaqueIDIndexMask)) 62 63/* 64 * Get the count part of an opaque_id 65 */ 66#define GetOpaqueIDCounterPart(id) (((uint32_t)(id)) >> kOpaqueIDIndexBits) 67 68/* 69 * Get the index part of an opaque_id 70 */ 71#define GetOpaqueIDIndexPart(id) (((uint32_t)(id)) & kOpaqueIDIndexMask) 72 73/*****************************************************************************/ 74 75/* 76 * Keep a 'list' of free records in the gOpaqueEntryArray table, using the .nextIndex field as 77 * the link to the next one. Nodes are put into this list at the end, and removed 78 * from the front, to try harder to keep from re-allocating a particular opaque id 79 * anytime soon after it has been disposed of. 80 */ 81 82struct OpaqueEntry 83{ 84 opaque_id id; /* when in use, this is the opaque ID; when not in use, the index part is zero */ 85 uint32_t nextIndex; /* linkage for the free list */ 86 void *data; /* when in use, this is pointer to the data; it is NULL otherwise */ 87}; 88typedef struct OpaqueEntry *OpaqueEntryArrayPtr; 89 90static pthread_mutex_t gOpaqueEntryMutex = PTHREAD_MUTEX_INITIALIZER; 91static u_int32_t gOpaqueEntriesAllocated = 0; 92static u_int32_t gOpaqueEntriesUsed = 0; 93static OpaqueEntryArrayPtr gOpaqueEntryArray = NULL; 94 95static u_int32_t gIndexOfFreeOpaqueEntryHead = 0; 96static u_int32_t gIndexOfFreeOpaqueEntryTail = 0; 97 98/*****************************************************************************/ 99 100/* 101 * AddToFreeList adds the OpaqueEntry at the specified index in the gOpaqueEntryArray array 102 * to the free list. 103 */ 104static void AddToFreeList(u_int32_t indexToFree) 105{ 106 OpaqueEntryArrayPtr freeEntry; 107 108 /* don't add the OpaqueEntry at index 0 to free list -- it just won't be used */ 109 if ( indexToFree != 0 ) 110 { 111 freeEntry = &gOpaqueEntryArray[indexToFree]; 112 freeEntry->data = 0; 113 freeEntry->nextIndex = 0; 114 115 /* Add this OpaqueEntry to the tail of the free list */ 116 if ( gIndexOfFreeOpaqueEntryTail != 0 ) 117 { 118 gOpaqueEntryArray[gIndexOfFreeOpaqueEntryTail].nextIndex = indexToFree; 119 } 120 gIndexOfFreeOpaqueEntryTail = indexToFree; 121 122 /* If the head of the free list is 0, then this OpaqueEntry is also the head */ 123 if ( gIndexOfFreeOpaqueEntryHead == 0 ) 124 { 125 gIndexOfFreeOpaqueEntryHead = indexToFree; 126 } 127 } 128} 129 130/*****************************************************************************/ 131 132/* 133 * RemoveFromFreeList removes a OpaqueEntry from the free list and returns 134 * its index in the gOpaqueEntryArray array. 135 */ 136static u_int32_t RemoveFromFreeList() 137{ 138 u_int32_t result; 139 140 /* are there any OpaqueEntries free? */ 141 if ( gIndexOfFreeOpaqueEntryHead != 0 ) 142 { 143 /* remove the OpaqueEntry from the head */ 144 result = gIndexOfFreeOpaqueEntryHead; 145 146 if ( gIndexOfFreeOpaqueEntryHead == gIndexOfFreeOpaqueEntryTail ) 147 { 148 gIndexOfFreeOpaqueEntryTail = 0; 149 } 150 151 gIndexOfFreeOpaqueEntryHead = gOpaqueEntryArray[gIndexOfFreeOpaqueEntryHead].nextIndex; 152 } 153 else 154 { 155 result = 0; 156 } 157 158 return ( result ); 159} 160 161/*****************************************************************************/ 162 163int AssignOpaqueID(void *inData, opaque_id *outID) 164{ 165 int error; 166 u_int32_t entryToUse; 167 168 require_action(outID != NULL, bad_parameter, error = EINVAL); 169 170 *outID = kInvalidOpaqueID; 171 172 error = pthread_mutex_lock(&gOpaqueEntryMutex); 173 require_noerr(error, pthread_mutex_lock); 174 175 /* 176 * If there aren't any items in the table, or if the number of free items is 177 * lower than we want, then grow the table. 178 */ 179 if ( (gIndexOfFreeOpaqueEntryHead == 0) || ((gOpaqueEntriesAllocated - gOpaqueEntriesUsed) < kOpaqueIDMinimumFree) ) 180 { 181 u_int32_t newCount; 182 183 newCount = MIN(gOpaqueEntriesAllocated + 2048, kOpaqueIDMaximumCount); 184 185 if ( gOpaqueEntriesAllocated < newCount ) 186 { 187 OpaqueEntryArrayPtr nuids; 188 189 nuids = (OpaqueEntryArrayPtr)realloc(gOpaqueEntryArray, sizeof(struct OpaqueEntry) * newCount); 190 191 if ( nuids != NULL ) 192 { 193 u_int32_t i; 194 195 gOpaqueEntryArray = nuids; 196 197 /* Add all the 'new' OpaqueEntry to the free list. */ 198 for ( i = 0; i < newCount - gOpaqueEntriesAllocated; ++i ) 199 { 200 /* set both count and index to 0 */ 201 gOpaqueEntryArray[gOpaqueEntriesAllocated + i].id = 0; 202 203 AddToFreeList(gOpaqueEntriesAllocated + i); 204 } 205 206 gOpaqueEntriesAllocated = newCount; 207 } 208 } 209 } 210 211 /* get index of an OpaqueEntry to use */ 212 entryToUse = RemoveFromFreeList(); 213 214 /* release the lock */ 215 pthread_mutex_unlock(&gOpaqueEntryMutex); 216 217 /* did we get an OpaqueEntry? */ 218 require_action((entryToUse != 0) && (entryToUse < gOpaqueEntriesAllocated), no_opaqueID, error = EINVAL); 219 220 /* the new id is created with the previous counter + 1, and the index */ 221 gOpaqueEntryArray[entryToUse].id = CreateOpaqueID(GetOpaqueIDCounterPart(gOpaqueEntryArray[entryToUse].id) + 1, entryToUse); 222 gOpaqueEntryArray[entryToUse].data = inData; 223 224 *outID = gOpaqueEntryArray[entryToUse].id; 225 226 ++gOpaqueEntriesUsed; 227 228no_opaqueID: 229pthread_mutex_lock: 230bad_parameter: 231 232 return ( error ); 233} 234 235/*****************************************************************************/ 236 237int DeleteOpaqueID(opaque_id inID) 238{ 239 int error; 240 uint32_t index; 241 242 error = pthread_mutex_lock(&gOpaqueEntryMutex); 243 require_noerr(error, pthread_mutex_lock); 244 245 index = GetOpaqueIDIndexPart(inID); 246 if ( (index != 0) && (index < gOpaqueEntriesAllocated) && (gOpaqueEntryArray[index].id == inID) ) 247 { 248 /* 249 * Keep the old counter so that next time we can increment the 250 * generation count and return a 'new' opaque ID which maps to this 251 * same index. The index is set to zero to indicate this entry is not 252 * in use. 253 */ 254 gOpaqueEntryArray[index].id = CreateOpaqueID(GetOpaqueIDCounterPart(inID), 0); 255 256 AddToFreeList(index); 257 --gOpaqueEntriesUsed; 258 } 259 else 260 { 261 error = EINVAL; 262 } 263 264 pthread_mutex_unlock(&gOpaqueEntryMutex); 265 266pthread_mutex_lock: 267 268 return ( error ); 269} 270 271/*****************************************************************************/ 272 273int RetrieveDataFromOpaqueID(opaque_id inID, void **outData) 274{ 275 int error; 276 uint32_t index; 277 278 error = pthread_mutex_lock(&gOpaqueEntryMutex); 279 require_noerr(error, pthread_mutex_lock); 280 281 index = GetOpaqueIDIndexPart(inID); 282 if ( (index != 0) && (index < gOpaqueEntriesAllocated) && (gOpaqueEntryArray[index].id == inID) ) 283 { 284 if (outData) 285 { 286 *outData = gOpaqueEntryArray[index].data; 287 } 288 } 289 else 290 { 291 error = EINVAL; 292 } 293 294 pthread_mutex_unlock(&gOpaqueEntryMutex); 295 296pthread_mutex_lock: 297 298 return ( error ); 299} 300 301/*****************************************************************************/ 302