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