1 /*
2  * Copyright (c) 2014 Apple Computer, Inc. All rights reserved.
3  *
4  * @APPLE_OSREFERENCE_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. The rights granted to you under the License
10  * may not be used to create, or enable the creation or redistribution of,
11  * unlawful or unlicensed copies of an Apple operating system, or to
12  * circumvent, violate, or enable the circumvention or violation of, any
13  * terms of an Apple operating system software license agreement.
14  *
15  * Please obtain a copy of the License at
16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
17  *
18  * The Original Code and all software distributed under the License are
19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23  * Please see the License for the specific language governing rights and
24  * limitations under the License.
25  *
26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27  */
28 
29 
30 #include <libkern/c++/OSContainers.h>
31 #include <libkern/c++/OSLib.h>
32 #include <libkern/c++/OSDictionary.h>
33 #include <libkern/OSSerializeBinary.h>
34 
35 #include <IOKit/IOLib.h>
36 
37 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
38 
39 #if 0
40 #define DEBG(fmt, args...)  { kprintf(fmt, args); }
41 #else
42 #define DEBG(fmt, args...)	{}
43 #endif
44 
45 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
46 
47 OSSerialize *OSSerialize::binaryWithCapacity(unsigned int inCapacity,
48 											 Editor editor, void * reference)
49 {
50 	OSSerialize *me;
51 
52     if (inCapacity < sizeof(uint32_t)) return (0);
53 	me = OSSerialize::withCapacity(inCapacity);
54     if (!me) return (0);
55 
56     me->binary        = true;
57     me->endCollection = true;
58     me->editor        = editor;
59     me->editRef       = reference;
60 
61 	bcopy(kOSSerializeBinarySignature, &me->data[0], sizeof(kOSSerializeBinarySignature));
62 	me->length = sizeof(kOSSerializeBinarySignature);
63 
64     return (me);
65 }
66 
67 bool OSSerialize::addBinary(const void * bits, size_t size)
68 {
69     unsigned int newCapacity;
70     size_t       alignSize;
71 
72 	alignSize = ((size + 3) & ~3L);
73 	newCapacity = length + alignSize;
74 	if (newCapacity >= capacity)
75 	{
76 	   newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) * capacityIncrement;
77 	   if (newCapacity > ensureCapacity(newCapacity)) return (false);
78     }
79 
80 	bcopy(bits, &data[length], size);
81 	length += alignSize;
82 
83 	return (true);
84 }
85 
86 bool OSSerialize::addBinaryObject(const OSMetaClassBase * o, uint32_t key,
87 								  const void * bits, size_t size)
88 {
89     unsigned int newCapacity;
90     size_t       alignSize;
91 
92     // add to tag array
93 	tags->setObject(o);
94 
95 	alignSize = ((size + sizeof(key) + 3) & ~3L);
96 	newCapacity = length + alignSize;
97 	if (newCapacity >= capacity)
98 	{
99 	   newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) * capacityIncrement;
100 	   if (newCapacity > ensureCapacity(newCapacity)) return (false);
101     }
102 
103     if (endCollection)
104     {
105          endCollection = false;
106          key |= kOSSerializeEndCollecton;
107     }
108 
109 	bcopy(&key, &data[length], sizeof(key));
110 	bcopy(bits, &data[length + sizeof(key)], size);
111 	length += alignSize;
112 
113 	return (true);
114 }
115 
116 bool OSSerialize::binarySerialize(const OSMetaClassBase *o)
117 {
118     OSDictionary * dict;
119     OSArray      * array;
120     OSSet        * set;
121     OSNumber     * num;
122     OSSymbol     * sym;
123     OSString     * str;
124     OSData       * ldata;
125     OSBoolean    * boo;
126 
127 	unsigned int  tagIdx;
128     uint32_t   i, key;
129     size_t     len;
130     bool       ok;
131 
132 	tagIdx = tags->getNextIndexOfObject(o, 0);
133 	// does it exist?
134 	if (-1U != tagIdx)
135 	{
136 		key = (kOSSerializeObject | tagIdx);
137 		if (endCollection)
138 		{
139 			 endCollection = false;
140 			 key |= kOSSerializeEndCollecton;
141 		}
142 		ok = addBinary(&key, sizeof(key));
143 		return (ok);
144 	}
145 
146 	if ((dict = OSDynamicCast(OSDictionary, o)))
147 	{
148 		key = (kOSSerializeDictionary | dict->count);
149 		ok = addBinaryObject(o, key, NULL, 0);
150 		for (i = 0; ok && (i < dict->count);)
151 		{
152 			const OSSymbol        * dictKey;
153 			const OSMetaClassBase * dictValue;
154 			const OSMetaClassBase * nvalue = 0;
155 
156 			dictKey = dict->dictionary[i].key;
157 			dictValue = dict->dictionary[i].value;
158 			i++;
159 			if (editor)
160 			{
161 				dictValue = nvalue = (*editor)(editRef, this, dict, dictKey, dictValue);
162 				if (!dictValue) dictValue = dict;
163 			}
164 			ok = binarySerialize(dictKey);
165 			if (!ok) break;
166 			endCollection = (i == dict->count);
167 			ok = binarySerialize(dictValue);
168 			if (!ok) ok = dictValue->serialize(this);
169 			if (nvalue) nvalue->release();
170 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
171 		}
172 	}
173 	else if ((array = OSDynamicCast(OSArray, o)))
174 	{
175 		key = (kOSSerializeArray | array->count);
176 		ok = addBinaryObject(o, key, NULL, 0);
177 		for (i = 0; ok && (i < array->count);)
178 		{
179 			i++;
180 			endCollection = (i == array->count);
181 			ok = binarySerialize(array->array[i-1]);
182 			if (!ok) ok = array->array[i-1]->serialize(this);
183 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
184 		}
185 	}
186 	else if ((set = OSDynamicCast(OSSet, o)))
187 	{
188 		key = (kOSSerializeSet | set->members->count);
189 		ok = addBinaryObject(o, key, NULL, 0);
190 		for (i = 0; ok && (i < set->members->count);)
191 		{
192 			i++;
193 			endCollection = (i == set->members->count);
194 			ok = binarySerialize(set->members->array[i-1]);
195 			if (!ok) ok = set->members->array[i-1]->serialize(this);
196 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
197 		}
198 	}
199 	else if ((num = OSDynamicCast(OSNumber, o)))
200 	{
201 		key = (kOSSerializeNumber | num->size);
202 		ok = addBinaryObject(o, key, &num->value, sizeof(num->value));
203 	}
204 	else if ((boo = OSDynamicCast(OSBoolean, o)))
205 	{
206 		key = (kOSSerializeBoolean | (kOSBooleanTrue == boo));
207 		ok = addBinaryObject(o, key, NULL, 0);
208 	}
209 	else if ((sym = OSDynamicCast(OSSymbol, o)))
210 	{
211 		len = (sym->getLength() + 1);
212 		key = (kOSSerializeSymbol | len);
213 		ok = addBinaryObject(o, key, sym->getCStringNoCopy(), len);
214 	}
215 	else if ((str = OSDynamicCast(OSString, o)))
216 	{
217 		len = (str->getLength() + 0);
218 		key = (kOSSerializeString | len);
219 		ok = addBinaryObject(o, key, str->getCStringNoCopy(), len);
220 	}
221 	else if ((ldata = OSDynamicCast(OSData, o)))
222 	{
223 		len = ldata->getLength();
224 		if (ldata->reserved && ldata->reserved->disableSerialization) len = 0;
225 		key = (kOSSerializeData | len);
226 		ok = addBinaryObject(o, key, ldata->getBytesNoCopy(), len);
227 	}
228 	else return (false);
229 
230     return (ok);
231 }
232 
233 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
234 
235 #define setAtIndex(v, idx, o)													        \
236 	if (idx >= v##Capacity)														        \
237 	{																			        \
238         if (v##Capacity >= v##CapacityMax) ok = false;                                  \
239         else																			\
240         {																			    \
241             uint32_t ncap = v##Capacity + 64;										    \
242             typeof(v##Array) nbuf = (typeof(v##Array)) kalloc_container(ncap * sizeof(o)); \
243             if (!nbuf) ok = false;													    \
244             else															            \
245             {															                \
246                 if (v##Array)															\
247                 {																		\
248                     bcopy(v##Array, nbuf, v##Capacity * sizeof(o));						\
249                     kfree(v##Array, v##Capacity * sizeof(o));							\
250                 }																		\
251                 v##Array    = nbuf;														\
252                 v##Capacity = ncap;														\
253             }															                \
254 	    }																			    \
255 	}																			        \
256 	if (ok) v##Array[idx] = o;
257 
258 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
259 
260 OSObject *
261 OSUnserializeBinary(const char *buffer, size_t bufferSize, OSString **errorString)
262 {
263 	OSObject ** objsArray;
264 	uint32_t    objsCapacity;
265 	enum      { objsCapacityMax = 16*1024*1024 };
266 	uint32_t    objsIdx;
267 
268 	OSObject ** stackArray;
269 	uint32_t    stackCapacity;
270 	enum      { stackCapacityMax = 64*1024 };
271 	uint32_t    stackIdx;
272 
273     OSObject     * result;
274     OSObject     * parent;
275     OSDictionary * dict;
276     OSArray      * array;
277     OSSet        * set;
278     OSDictionary * newDict;
279     OSArray      * newArray;
280     OSSet        * newSet;
281     OSObject     * o;
282     OSSymbol     * sym;
283     OSString     * str;
284 
285     size_t           bufferPos;
286     const uint32_t * next;
287     uint32_t         key, len, wordLen;
288     bool             end, newCollect, isRef;
289     unsigned long long value;
290     bool ok;
291 
292 	if (errorString) *errorString = 0;
293 	if (bufferSize < sizeof(kOSSerializeBinarySignature)) return (NULL);
294 	if (0 != strcmp(kOSSerializeBinarySignature, buffer)) return (NULL);
295 	if (3 & ((uintptr_t) buffer)) return (NULL);
296 	bufferPos = sizeof(kOSSerializeBinarySignature);
297 	next = (typeof(next)) (((uintptr_t) buffer) + bufferPos);
298 
299 	DEBG("---------OSUnserializeBinary(%p)\n", buffer);
300 
301 	objsArray = stackArray    = NULL;
302 	objsIdx   = objsCapacity  = 0;
303 	stackIdx  = stackCapacity = 0;
304 
305     result   = 0;
306     parent   = 0;
307 	dict     = 0;
308 	array    = 0;
309 	set      = 0;
310 	sym      = 0;
311 
312 	ok = true;
313 	while (ok)
314 	{
315 		bufferPos += sizeof(*next);
316 		if (!(ok = (bufferPos <= bufferSize))) break;
317 		key = *next++;
318 
319         len = (key & kOSSerializeDataMask);
320         wordLen = (len + 3) >> 2;
321 		end = (0 != (kOSSerializeEndCollecton & key));
322         DEBG("key 0x%08x: 0x%04x, %d\n", key, len, end);
323 
324         newCollect = isRef = false;
325 		o = 0; newDict = 0; newArray = 0; newSet = 0;
326 
327 		switch (kOSSerializeTypeMask & key)
328 		{
329 		    case kOSSerializeDictionary:
330 				o = newDict = OSDictionary::withCapacity(len);
331 				newCollect = (len != 0);
332 		        break;
333 		    case kOSSerializeArray:
334 				o = newArray = OSArray::withCapacity(len);
335 				newCollect = (len != 0);
336 		        break;
337 		    case kOSSerializeSet:
338 				o = newSet = OSSet::withCapacity(len);
339 				newCollect = (len != 0);
340 		        break;
341 
342 		    case kOSSerializeObject:
343 				if (len >= objsIdx) break;
344 				o = objsArray[len];
345 				isRef = true;
346 				break;
347 
348 		    case kOSSerializeNumber:
349 				bufferPos += sizeof(long long);
350 				if (bufferPos > bufferSize) break;
351 		        if ((len != 32) && (len != 64) && (len != 16) && (len != 8)) break;
352 		    	value = next[1];
353 		    	value <<= 32;
354 		    	value |= next[0];
355 		    	o = OSNumber::withNumber(value, len);
356 		    	next += 2;
357 		        break;
358 
359 		    case kOSSerializeSymbol:
360 				bufferPos += (wordLen * sizeof(uint32_t));
361 				if (bufferPos > bufferSize)           break;
362 				if (len < 2)                          break;
363 				if (0 != ((const char *)next)[len-1]) break;
364 		        o = (OSObject *) OSSymbol::withCString((const char *) next);
365 		        next += wordLen;
366 		        break;
367 
368 		    case kOSSerializeString:
369 				bufferPos += (wordLen * sizeof(uint32_t));
370 				if (bufferPos > bufferSize) break;
371 		        o = OSString::withStringOfLength((const char *) next, len);
372 		        next += wordLen;
373 		        break;
374 
375     	    case kOSSerializeData:
376 				bufferPos += (wordLen * sizeof(uint32_t));
377 				if (bufferPos > bufferSize) break;
378 		        o = OSData::withBytes(next, len);
379 		        next += wordLen;
380 		        break;
381 
382     	    case kOSSerializeBoolean:
383 				o = (len ? kOSBooleanTrue : kOSBooleanFalse);
384 		        break;
385 
386 		    default:
387 		        break;
388 		}
389 
390 		if (!(ok = (o != 0))) break;
391 
392 		if (!isRef)
393 		{
394 			setAtIndex(objs, objsIdx, o);
395 			if (!ok)
396 			{
397 			    o->release();
398                 break;
399             }
400 			objsIdx++;
401 		}
402 
403 		if (dict)
404 		{
405 			if (!sym) sym = (OSSymbol *) o;
406 			else
407 			{
408                 str = sym;
409 				sym = OSDynamicCast(OSSymbol, sym);
410 				if (!sym && (str = OSDynamicCast(OSString, str)))
411 				{
412 				    sym = (OSSymbol *) OSSymbol::withString(str);
413                     ok = (sym != 0);
414                     if (!ok) break;
415 				}
416 				DEBG("%s = %s\n", sym->getCStringNoCopy(), o->getMetaClass()->getClassName());
417 				if (o != dict) ok = dict->setObject(sym, o);
418                 if (sym && (sym != str)) sym->release();
419 				sym = 0;
420 			}
421 		}
422 		else if (array)  ok = array->setObject(o);
423 		else if (set)    ok = set->setObject(o);
424 		else if (result) ok = false;
425 		else
426 		{
427 		    assert(!parent);
428 		    result = o;
429 		}
430 
431 		if (!ok) break;
432 
433 		if (newCollect)
434 		{
435 			if (!end)
436 			{
437 				stackIdx++;
438 				setAtIndex(stack, stackIdx, parent);
439 				if (!ok) break;
440 			}
441 			DEBG("++stack[%d] %p\n", stackIdx, parent);
442 			parent = o;
443 			dict   = newDict;
444 			array  = newArray;
445 			set    = newSet;
446 			end    = false;
447 		}
448 
449 		if (end)
450 		{
451 			if (!stackIdx) break;
452 			parent = stackArray[stackIdx];
453 			DEBG("--stack[%d] %p\n", stackIdx, parent);
454 			stackIdx--;
455 			set   = 0;
456 			dict  = 0;
457 			array = 0;
458 			if (!(dict = OSDynamicCast(OSDictionary, parent)))
459 			{
460 				if (!(array = OSDynamicCast(OSArray, parent))) ok = (0 != (set = OSDynamicCast(OSSet, parent)));
461 			}
462 		}
463 	}
464 	DEBG("ret %p\n", result);
465 
466 	if (!ok) result = 0;
467 
468 	if (objsCapacity)
469 	{
470         for (len = (result != 0); len < objsIdx; len++) objsArray[len]->release();
471 	    kfree(objsArray,  objsCapacity  * sizeof(*objsArray));
472     }
473 	if (stackCapacity) kfree(stackArray, stackCapacity * sizeof(*stackArray));
474 
475 	return (result);
476 }
477