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