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 	if (os_add_overflow(size, 3, &alignSize)) return (false);
73 	alignSize &= ~3L;
74 	if (os_add_overflow(length, alignSize, &newCapacity)) return (false);
75 	if (newCapacity >= capacity)
76 	{
77 	   newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) * capacityIncrement;
78 	   if (newCapacity > ensureCapacity(newCapacity)) return (false);
79     }
80 
81 	bcopy(bits, &data[length], size);
82 	length += alignSize;
83 
84 	return (true);
85 }
86 
87 bool OSSerialize::addBinaryObject(const OSMetaClassBase * o, uint32_t key,
88 								  const void * bits, size_t size)
89 {
90     unsigned int newCapacity;
91     size_t       alignSize;
92 
93     // add to tag array
94 	tags->setObject(o);
95 
96 	if (os_add3_overflow(size, sizeof(key), 3, &alignSize)) return (false);
97 	alignSize &= ~3L;
98 	if (os_add_overflow(length, alignSize, &newCapacity)) return (false);
99 	if (newCapacity >= capacity)
100 	{
101 	   newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) * capacityIncrement;
102 	   if (newCapacity > ensureCapacity(newCapacity)) return (false);
103     }
104 
105     if (endCollection)
106     {
107          endCollection = false;
108          key |= kOSSerializeEndCollecton;
109     }
110 
111 	bcopy(&key, &data[length], sizeof(key));
112 	bcopy(bits, &data[length + sizeof(key)], size);
113 	length += alignSize;
114 
115 	return (true);
116 }
117 
118 bool OSSerialize::binarySerialize(const OSMetaClassBase *o)
119 {
120     OSDictionary * dict;
121     OSArray      * array;
122     OSSet        * set;
123     OSNumber     * num;
124     OSSymbol     * sym;
125     OSString     * str;
126     OSData       * ldata;
127     OSBoolean    * boo;
128 
129 	unsigned int  tagIdx;
130     uint32_t   i, key;
131     size_t     len;
132     bool       ok;
133 
134 	tagIdx = tags->getNextIndexOfObject(o, 0);
135 	// does it exist?
136 	if (-1U != tagIdx)
137 	{
138 		key = (kOSSerializeObject | tagIdx);
139 		if (endCollection)
140 		{
141 			 endCollection = false;
142 			 key |= kOSSerializeEndCollecton;
143 		}
144 		ok = addBinary(&key, sizeof(key));
145 		return (ok);
146 	}
147 
148 	if ((dict = OSDynamicCast(OSDictionary, o)))
149 	{
150 		key = (kOSSerializeDictionary | dict->count);
151 		ok = addBinaryObject(o, key, NULL, 0);
152 		for (i = 0; ok && (i < dict->count);)
153 		{
154 			const OSSymbol        * dictKey;
155 			const OSMetaClassBase * dictValue;
156 			const OSMetaClassBase * nvalue = 0;
157 
158 			dictKey = dict->dictionary[i].key;
159 			dictValue = dict->dictionary[i].value;
160 			i++;
161 			if (editor)
162 			{
163 				dictValue = nvalue = (*editor)(editRef, this, dict, dictKey, dictValue);
164 				if (!dictValue) dictValue = dict;
165 			}
166 			ok = binarySerialize(dictKey);
167 			if (!ok) break;
168 			endCollection = (i == dict->count);
169 			ok = binarySerialize(dictValue);
170 			if (!ok) ok = dictValue->serialize(this);
171 			if (nvalue) nvalue->release();
172 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
173 		}
174 	}
175 	else if ((array = OSDynamicCast(OSArray, o)))
176 	{
177 		key = (kOSSerializeArray | array->count);
178 		ok = addBinaryObject(o, key, NULL, 0);
179 		for (i = 0; ok && (i < array->count);)
180 		{
181 			i++;
182 			endCollection = (i == array->count);
183 			ok = binarySerialize(array->array[i-1]);
184 			if (!ok) ok = array->array[i-1]->serialize(this);
185 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
186 		}
187 	}
188 	else if ((set = OSDynamicCast(OSSet, o)))
189 	{
190 		key = (kOSSerializeSet | set->members->count);
191 		ok = addBinaryObject(o, key, NULL, 0);
192 		for (i = 0; ok && (i < set->members->count);)
193 		{
194 			i++;
195 			endCollection = (i == set->members->count);
196 			ok = binarySerialize(set->members->array[i-1]);
197 			if (!ok) ok = set->members->array[i-1]->serialize(this);
198 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
199 		}
200 	}
201 	else if ((num = OSDynamicCast(OSNumber, o)))
202 	{
203 		key = (kOSSerializeNumber | num->size);
204 		ok = addBinaryObject(o, key, &num->value, sizeof(num->value));
205 	}
206 	else if ((boo = OSDynamicCast(OSBoolean, o)))
207 	{
208 		key = (kOSSerializeBoolean | (kOSBooleanTrue == boo));
209 		ok = addBinaryObject(o, key, NULL, 0);
210 	}
211 	else if ((sym = OSDynamicCast(OSSymbol, o)))
212 	{
213 		len = (sym->getLength() + 1);
214 		key = (kOSSerializeSymbol | len);
215 		ok = addBinaryObject(o, key, sym->getCStringNoCopy(), len);
216 	}
217 	else if ((str = OSDynamicCast(OSString, o)))
218 	{
219 		len = (str->getLength() + 0);
220 		key = (kOSSerializeString | len);
221 		ok = addBinaryObject(o, key, str->getCStringNoCopy(), len);
222 	}
223 	else if ((ldata = OSDynamicCast(OSData, o)))
224 	{
225 		len = ldata->getLength();
226 		if (ldata->reserved && ldata->reserved->disableSerialization) len = 0;
227 		key = (kOSSerializeData | len);
228 		ok = addBinaryObject(o, key, ldata->getBytesNoCopy(), len);
229 	}
230 	else return (false);
231 
232     return (ok);
233 }
234 
235 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
236 
237 #define setAtIndex(v, idx, o)													        \
238 	if (idx >= v##Capacity)														        \
239 	{																			        \
240         if (v##Capacity >= v##CapacityMax) ok = false;                                  \
241         else																			\
242         {																			    \
243             uint32_t ncap = v##Capacity + 64;										    \
244             typeof(v##Array) nbuf = (typeof(v##Array)) kalloc_container(ncap * sizeof(o)); \
245             if (!nbuf) ok = false;													    \
246             else															            \
247             {															                \
248                 if (v##Array)															\
249                 {																		\
250                     bcopy(v##Array, nbuf, v##Capacity * sizeof(o));						\
251                     kfree(v##Array, v##Capacity * sizeof(o));							\
252                 }																		\
253                 v##Array    = nbuf;														\
254                 v##Capacity = ncap;														\
255             }															                \
256 	    }																			    \
257 	}																			        \
258 	if (ok) v##Array[idx] = o;
259 
260 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
261 
262 OSObject *
263 OSUnserializeBinary(const char *buffer, size_t bufferSize, OSString **errorString)
264 {
265 	OSObject ** objsArray;
266 	uint32_t    objsCapacity;
267 	enum      { objsCapacityMax = 16*1024*1024 };
268 	uint32_t    objsIdx;
269 
270 	OSObject ** stackArray;
271 	uint32_t    stackCapacity;
272 	enum      { stackCapacityMax = 64 };
273 	uint32_t    stackIdx;
274 
275     OSObject     * result;
276     OSObject     * parent;
277     OSDictionary * dict;
278     OSArray      * array;
279     OSSet        * set;
280     OSDictionary * newDict;
281     OSArray      * newArray;
282     OSSet        * newSet;
283     OSObject     * o;
284     OSSymbol     * sym;
285     OSString     * str;
286 
287     size_t           bufferPos;
288     const uint32_t * next;
289     uint32_t         key, len, wordLen;
290     bool             end, newCollect, isRef;
291     unsigned long long value;
292     bool ok;
293 
294 	if (errorString) *errorString = 0;
295 	if (bufferSize < sizeof(kOSSerializeBinarySignature)) return (NULL);
296 	if (0 != strcmp(kOSSerializeBinarySignature, buffer)) return (NULL);
297 	if (3 & ((uintptr_t) buffer)) return (NULL);
298 	bufferPos = sizeof(kOSSerializeBinarySignature);
299 	next = (typeof(next)) (((uintptr_t) buffer) + bufferPos);
300 
301 	DEBG("---------OSUnserializeBinary(%p)\n", buffer);
302 
303 	objsArray = stackArray    = NULL;
304 	objsIdx   = objsCapacity  = 0;
305 	stackIdx  = stackCapacity = 0;
306 
307     result   = 0;
308     parent   = 0;
309 	dict     = 0;
310 	array    = 0;
311 	set      = 0;
312 	sym      = 0;
313 
314 	ok = true;
315 	while (ok)
316 	{
317 		bufferPos += sizeof(*next);
318 		if (!(ok = (bufferPos <= bufferSize))) break;
319 		key = *next++;
320 
321         len = (key & kOSSerializeDataMask);
322         wordLen = (len + 3) >> 2;
323 		end = (0 != (kOSSerializeEndCollecton & key));
324         DEBG("key 0x%08x: 0x%04x, %d\n", key, len, end);
325 
326         newCollect = isRef = false;
327 		o = 0; newDict = 0; newArray = 0; newSet = 0;
328 
329 		switch (kOSSerializeTypeMask & key)
330 		{
331 		    case kOSSerializeDictionary:
332 				o = newDict = OSDictionary::withCapacity(len);
333 				newCollect = (len != 0);
334 		        break;
335 		    case kOSSerializeArray:
336 				o = newArray = OSArray::withCapacity(len);
337 				newCollect = (len != 0);
338 		        break;
339 		    case kOSSerializeSet:
340 				o = newSet = OSSet::withCapacity(len);
341 				newCollect = (len != 0);
342 		        break;
343 
344 		    case kOSSerializeObject:
345 				if (len >= objsIdx) break;
346 				o = objsArray[len];
347 				isRef = true;
348 				break;
349 
350 		    case kOSSerializeNumber:
351 				bufferPos += sizeof(long long);
352 				if (bufferPos > bufferSize) break;
353 		        if ((len != 32) && (len != 64) && (len != 16) && (len != 8)) break;
354 		    	value = next[1];
355 		    	value <<= 32;
356 		    	value |= next[0];
357 		    	o = OSNumber::withNumber(value, len);
358 		    	next += 2;
359 		        break;
360 
361 		    case kOSSerializeSymbol:
362 				bufferPos += (wordLen * sizeof(uint32_t));
363 				if (bufferPos > bufferSize)           break;
364 				if (len < 2)                          break;
365 				if (0 != ((const char *)next)[len-1]) break;
366 		        o = (OSObject *) OSSymbol::withCString((const char *) next);
367 		        next += wordLen;
368 		        break;
369 
370 		    case kOSSerializeString:
371 				bufferPos += (wordLen * sizeof(uint32_t));
372 				if (bufferPos > bufferSize) break;
373 		        o = OSString::withStringOfLength((const char *) next, len);
374 		        next += wordLen;
375 		        break;
376 
377     	    case kOSSerializeData:
378 				bufferPos += (wordLen * sizeof(uint32_t));
379 				if (bufferPos > bufferSize) break;
380 		        o = OSData::withBytes(next, len);
381 		        next += wordLen;
382 		        break;
383 
384     	    case kOSSerializeBoolean:
385 				o = (len ? kOSBooleanTrue : kOSBooleanFalse);
386 		        break;
387 
388 		    default:
389 		        break;
390 		}
391 
392 		if (!(ok = (o != 0))) break;
393 
394 		if (!isRef)
395 		{
396 			setAtIndex(objs, objsIdx, o);
397 			if (!ok)
398 			{
399 			    o->release();
400                 break;
401             }
402 			objsIdx++;
403 		}
404 
405 		if (dict)
406 		{
407 			if (!sym) sym = (OSSymbol *) o;
408 			else
409 			{
410                 str = sym;
411 				sym = OSDynamicCast(OSSymbol, sym);
412 				if (!sym && (str = OSDynamicCast(OSString, str)))
413 				{
414 				    sym = (OSSymbol *) OSSymbol::withString(str);
415                     ok = (sym != 0);
416                     if (!ok) break;
417 				}
418 				DEBG("%s = %s\n", sym->getCStringNoCopy(), o->getMetaClass()->getClassName());
419 				if (o != dict) ok = dict->setObject(sym, o);
420                 if (sym && (sym != str)) sym->release();
421 				sym = 0;
422 			}
423 		}
424 		else if (array)  ok = array->setObject(o);
425 		else if (set)    ok = set->setObject(o);
426 		else if (result) ok = false;
427 		else
428 		{
429 		    assert(!parent);
430 		    result = o;
431 		}
432 
433 		if (!ok) break;
434 
435         if (end) parent = 0;
436 		if (newCollect)
437 		{
438             stackIdx++;
439             setAtIndex(stack, stackIdx, parent);
440             if (!ok) break;
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             while (stackIdx)
452             {
453                 parent = stackArray[stackIdx];
454                 DEBG("--stack[%d] %p\n", stackIdx, parent);
455                 stackIdx--;
456                 if (parent) break;
457             }
458             if (!parent) break;
459 			set   = 0;
460 			dict  = 0;
461 			array = 0;
462 			if (!(dict = OSDynamicCast(OSDictionary, parent)))
463 			{
464 				if (!(array = OSDynamicCast(OSArray, parent))) ok = (0 != (set = OSDynamicCast(OSSet, parent)));
465 			}
466 		}
467 	}
468 	DEBG("ret %p\n", result);
469 
470 	if (!ok) result = 0;
471 
472 	if (objsCapacity)
473 	{
474         for (len = (result != 0); len < objsIdx; len++) objsArray[len]->release();
475 	    kfree(objsArray,  objsCapacity  * sizeof(*objsArray));
476     }
477 	if (stackCapacity) kfree(stackArray, stackCapacity * sizeof(*stackArray));
478 
479 	return (result);
480 }
481