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++/OSSharedPtr.h>
31 #include <libkern/OSSerializeBinary.h>
32 #include <libkern/c++/OSContainers.h>
33 #include <libkern/c++/OSLib.h>
34 #include <libkern/c++/OSDictionary.h>
35 #include <libkern/OSSerializeBinary.h>
36 #include <libkern/c++/OSSharedPtr.h>
37 
38 #include <IOKit/IOLib.h>
39 
40 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
41 
42 #if 0
43 #define DEBG(fmt, args ...)  { kprintf(fmt, args); }
44 #else
45 #define DEBG(fmt, args ...)      {}
46 #endif
47 
48 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
49 
50 OSSerialize *
51 OSSerialize::binaryWithCapacity(unsigned int inCapacity,
52     Editor editor, void * reference)
53 {
54 	OSSerialize *me;
55 
56 	if (inCapacity < sizeof(uint32_t)) {
57 		return NULL;
58 	}
59 	me = OSSerialize::withCapacity(inCapacity);
60 	if (!me) {
61 		return NULL;
62 	}
63 
64 	me->binary        = true;
65 	me->endCollection = true;
66 	me->editor        = editor;
67 	me->editRef       = reference;
68 
69 	bcopy(kOSSerializeBinarySignature, &me->data[0], sizeof(kOSSerializeBinarySignature));
70 	me->length = sizeof(kOSSerializeBinarySignature);
71 
72 	return me;
73 }
74 
75 bool
76 OSSerialize::addBinary(const void * bits, size_t size)
77 {
78 	unsigned int newCapacity;
79 	size_t       alignSize;
80 
81 	if (os_add_overflow(size, 3, &alignSize)) {
82 		return false;
83 	}
84 	alignSize &= ~3L;
85 	if (os_add_overflow(length, alignSize, &newCapacity)) {
86 		return false;
87 	}
88 	if (newCapacity >= capacity) {
89 		newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) * capacityIncrement;
90 		if (newCapacity < capacity) {
91 			return false;
92 		}
93 		if (newCapacity > ensureCapacity(newCapacity)) {
94 			return false;
95 		}
96 	}
97 
98 	bcopy(bits, &data[length], size);
99 	length += alignSize;
100 
101 	return true;
102 }
103 
104 void
105 OSSerialize::setIndexed(bool index __unused)
106 {
107 	assert(index && !indexData);
108 	indexData = OSData::withCapacity(256);
109 	assert(indexData);
110 }
111 
112 bool
113 OSSerialize::addBinaryObject(const OSMetaClassBase * o, uint32_t key,
114     const void * bits, uint32_t size,
115     uint32_t * startCollection)
116 {
117 	unsigned int newCapacity;
118 	size_t       alignSize;
119 	size_t       headerSize;
120 
121 	// add to tag array
122 	tags->setObject(o);
123 
124 	headerSize = sizeof(key);
125 	if (indexData) {
126 		uint32_t offset = length;
127 		if (startCollection) {
128 			*startCollection = offset;
129 			headerSize += sizeof(uint32_t);
130 		}
131 		offset /= sizeof(uint32_t);
132 		indexData->appendBytes(&offset, sizeof(offset));
133 	}
134 
135 	if (os_add3_overflow(size, headerSize, 3, &alignSize)) {
136 		return false;
137 	}
138 	alignSize &= ~3L;
139 	if (os_add_overflow(length, alignSize, &newCapacity)) {
140 		return false;
141 	}
142 	if (newCapacity >= capacity) {
143 		newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) * capacityIncrement;
144 		if (newCapacity < capacity) {
145 			return false;
146 		}
147 		if (newCapacity > ensureCapacity(newCapacity)) {
148 			return false;
149 		}
150 	}
151 
152 	if (endCollection) {
153 		endCollection = false;
154 		key |= kOSSerializeEndCollecton;
155 	}
156 
157 	bcopy(&key, &data[length], sizeof(key));
158 	bcopy(bits, &data[length + headerSize], size);
159 	length += alignSize;
160 
161 	return true;
162 }
163 
164 void
165 OSSerialize::endBinaryCollection(uint32_t startCollection)
166 {
167 	uint32_t clength;
168 
169 	if (!indexData) {
170 		return;
171 	}
172 
173 	assert(length > startCollection);
174 	if (length <= startCollection) {
175 		return;
176 	}
177 
178 	clength = length - startCollection;
179 	assert(!(clength & 3));
180 	clength /= sizeof(uint32_t);
181 
182 	memcpy(&data[startCollection + sizeof(uint32_t)], &clength, sizeof(clength));
183 }
184 
185 bool
186 OSSerialize::binarySerialize(const OSMetaClassBase *o)
187 {
188 	bool ok;
189 	uint32_t header;
190 
191 	ok = binarySerializeInternal(o);
192 	if (!ok) {
193 		return ok;
194 	}
195 
196 	if (indexData) {
197 		header = indexData->getLength() / sizeof(uint32_t);
198 		assert(header <= kOSSerializeDataMask);
199 		header <<= 8;
200 		header |= kOSSerializeIndexedBinarySignature;
201 
202 		memcpy(&data[0], &header, sizeof(header));
203 	}
204 
205 	return ok;
206 }
207 
208 bool
209 OSSerialize::binarySerializeInternal(const OSMetaClassBase *o)
210 {
211 	OSDictionary * dict;
212 	OSArray      * array;
213 	OSSet        * set;
214 	OSNumber     * num;
215 	OSSymbol     * sym;
216 	OSString     * str;
217 	OSData       * ldata;
218 	OSBoolean    * boo;
219 
220 	unsigned int  tagIdx;
221 	uint32_t   i, key, startCollection;
222 	uint32_t   len;
223 	bool       ok;
224 
225 	tagIdx = tags->getNextIndexOfObject(o, 0);
226 	// does it exist?
227 	if (-1U != tagIdx) {
228 		if (indexData) {
229 			assert(indexData->getLength() > (tagIdx * sizeof(uint32_t)));
230 			tagIdx = ((const uint32_t *)indexData->getBytesNoCopy())[tagIdx];
231 			assert(tagIdx <= kOSSerializeDataMask);
232 		}
233 		key = (kOSSerializeObject | tagIdx);
234 		if (endCollection) {
235 			endCollection = false;
236 			key |= kOSSerializeEndCollecton;
237 		}
238 		ok = addBinary(&key, sizeof(key));
239 		return ok;
240 	}
241 
242 	if ((dict = OSDynamicCast(OSDictionary, o))) {
243 		key = (kOSSerializeDictionary | dict->count);
244 		ok = addBinaryObject(o, key, NULL, 0, &startCollection);
245 		for (i = 0; ok && (i < dict->count);) {
246 			const OSSymbol        * dictKey;
247 			const OSMetaClassBase * dictValue;
248 			const OSMetaClassBase * nvalue = NULL;
249 
250 			dictKey = dict->dictionary[i].key;
251 			dictValue = dict->dictionary[i].value;
252 			i++;
253 			if (editor) {
254 				dictValue = nvalue = (*editor)(editRef, this, dict, dictKey, dictValue);
255 				if (!dictValue) {
256 					dictValue = dict;
257 				}
258 			}
259 			ok = binarySerialize(dictKey);
260 			if (!ok) {
261 				break;
262 			}
263 			endCollection = (i == dict->count);
264 			ok = binarySerialize(dictValue);
265 			if (!ok) {
266 				ok = dictValue->serialize(this);
267 			}
268 			if (nvalue) {
269 				nvalue->release();
270 			}
271 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
272 		}
273 		endBinaryCollection(startCollection);
274 	} else if ((array = OSDynamicCast(OSArray, o))) {
275 		key = (kOSSerializeArray | array->count);
276 		ok = addBinaryObject(o, key, NULL, 0, &startCollection);
277 		for (i = 0; ok && (i < array->count);) {
278 			i++;
279 			endCollection = (i == array->count);
280 			ok = binarySerialize(array->array[i - 1]);
281 			if (!ok) {
282 				ok = array->array[i - 1]->serialize(this);
283 			}
284 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
285 		}
286 		endBinaryCollection(startCollection);
287 	} else if ((set = OSDynamicCast(OSSet, o))) {
288 		key = (kOSSerializeSet | set->members->count);
289 		ok = addBinaryObject(o, key, NULL, 0, &startCollection);
290 		for (i = 0; ok && (i < set->members->count);) {
291 			i++;
292 			endCollection = (i == set->members->count);
293 			ok = binarySerialize(set->members->array[i - 1]);
294 			if (!ok) {
295 				ok = set->members->array[i - 1]->serialize(this);
296 			}
297 //			if (!ok) ok = binarySerialize(kOSBooleanFalse);
298 		}
299 		endBinaryCollection(startCollection);
300 	} else if ((num = OSDynamicCast(OSNumber, o))) {
301 		key = (kOSSerializeNumber | num->size);
302 		ok = addBinaryObject(o, key, &num->value, sizeof(num->value), NULL);
303 	} else if ((boo = OSDynamicCast(OSBoolean, o))) {
304 		key = (kOSSerializeBoolean | (kOSBooleanTrue == boo));
305 		ok = addBinaryObject(o, key, NULL, 0, NULL);
306 	} else if ((sym = OSDynamicCast(OSSymbol, o))) {
307 		len = (sym->getLength() + 1);
308 		key = (kOSSerializeSymbol | len);
309 		ok = addBinaryObject(o, key, sym->getCStringNoCopy(), len, NULL);
310 	} else if ((str = OSDynamicCast(OSString, o))) {
311 		len = (str->getLength() + ((indexData != NULL) ? 1 : 0));
312 		key = (kOSSerializeString | len);
313 		ok = addBinaryObject(o, key, str->getCStringNoCopy(), len, NULL);
314 	} else if ((ldata = OSDynamicCast(OSData, o))) {
315 		len = ldata->getLength();
316 		if (ldata->reserved && ldata->reserved->disableSerialization) {
317 			len = 0;
318 		}
319 		key = (kOSSerializeData | len);
320 		ok = addBinaryObject(o, key, ldata->getBytesNoCopy(), len, NULL);
321 	} else {
322 		return false;
323 	}
324 
325 	return ok;
326 }
327 
328 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
329 
330 #define setAtIndex(v, idx, o)                                                                                                           \
331 	if (idx >= v##Capacity)                                                                                                                 \
332 	{                                                                                                                                                               \
333 	if (v##Capacity >= v##CapacityMax) ok = false;                                  \
334 	else                                                                                                                                                    \
335 	{                                                                                                                                                           \
336 	    uint32_t ncap = v##Capacity + 64;                                                                               \
337 	    typeof(v##Array) nbuf = (typeof(v##Array)) kalloc_container(ncap * sizeof(o)); \
338 	    if (!nbuf) ok = false;                                                                                                          \
339 	    else                                                                                                                                    \
340 	    {                                                                                                                                   \
341 	        if (v##Array)                                                                                                                   \
342 	        {                                                                                                                                               \
343 	            bcopy(v##Array, nbuf, v##Capacity * sizeof(o));                                             \
344 	            kfree(v##Array, v##Capacity * sizeof(o));                                                   \
345 	        }                                                                                                                                               \
346 	        v##Array    = nbuf;                                                                                                             \
347 	        v##Capacity = ncap;                                                                                                             \
348 	    }                                                                                                                                   \
349 	    }                                                                                                                                                       \
350 	}                                                                                                                                                               \
351 	if (ok) v##Array[idx] = o;
352 
353 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
354 
355 OSObject *
356 OSUnserializeBinary(const char *buffer, size_t bufferSize, OSString **errorString)
357 {
358 	OSObject ** objsArray;
359 	uint32_t    objsCapacity;
360 	enum      { objsCapacityMax = 16 * 1024 * 1024 };
361 	uint32_t    objsIdx;
362 
363 	OSObject ** stackArray;
364 	uint32_t    stackCapacity;
365 	enum      { stackCapacityMax = 64 };
366 	uint32_t    stackIdx;
367 
368 	OSObject     * result;
369 	OSObject     * parent;
370 	OSDictionary * dict;
371 	OSArray      * array;
372 	OSSet        * set;
373 	OSDictionary * newDict;
374 	OSArray      * newArray;
375 	OSSet        * newSet;
376 	OSObject     * o;
377 	OSSymbol     * sym;
378 	OSString     * str;
379 
380 	size_t           bufferPos;
381 	const uint32_t * next;
382 	uint32_t         key, len, wordLen, length;
383 	bool             end, newCollect, isRef;
384 	unsigned long long value;
385 	bool ok, indexed, hasLength;
386 
387 	indexed = false;
388 	if (errorString) {
389 		*errorString = NULL;
390 	}
391 
392 	if (bufferSize < sizeof(kOSSerializeBinarySignature)) {
393 		return NULL;
394 	}
395 	if (kOSSerializeIndexedBinarySignature == (((const uint8_t *) buffer)[0])) {
396 		indexed = true;
397 	} else if (0 != strcmp(kOSSerializeBinarySignature, buffer)) {
398 		return NULL;
399 	}
400 	if (3 & ((uintptr_t) buffer)) {
401 		return NULL;
402 	}
403 
404 	bufferPos = sizeof(kOSSerializeBinarySignature);
405 	next = (typeof(next))(((uintptr_t) buffer) + bufferPos);
406 
407 	DEBG("---------OSUnserializeBinary(%p)\n", buffer);
408 
409 	objsArray = stackArray    = NULL;
410 	objsIdx   = objsCapacity  = 0;
411 	stackIdx  = stackCapacity = 0;
412 
413 	result   = NULL;
414 	parent   = NULL;
415 	dict     = NULL;
416 	array    = NULL;
417 	set      = NULL;
418 	sym      = NULL;
419 
420 	ok = true;
421 	while (ok) {
422 		bufferPos += sizeof(*next);
423 		if (!(ok = (bufferPos <= bufferSize))) {
424 			break;
425 		}
426 		key = *next++;
427 		length = 0;
428 
429 		len = (key & kOSSerializeDataMask);
430 		wordLen = (len + 3) >> 2;
431 		end = (0 != (kOSSerializeEndCollecton & key));
432 		DEBG("key 0x%08x: 0x%04x, %d\n", key, len, end);
433 
434 		newCollect = isRef = hasLength = false;
435 		o = NULL; newDict = NULL; newArray = NULL; newSet = NULL;
436 
437 		switch (kOSSerializeTypeMask & key) {
438 		case kOSSerializeDictionary:
439 			o = newDict = OSDictionary::withCapacity(len);
440 			newCollect = (len != 0);
441 			hasLength  = indexed;
442 			break;
443 		case kOSSerializeArray:
444 			o = newArray = OSArray::withCapacity(len);
445 			newCollect = (len != 0);
446 			hasLength  = indexed;
447 			break;
448 		case kOSSerializeSet:
449 			o = newSet = OSSet::withCapacity(len);
450 			newCollect = (len != 0);
451 			hasLength  = indexed;
452 			break;
453 
454 		case kOSSerializeObject:
455 			if (len >= objsIdx) {
456 				break;
457 			}
458 			o = objsArray[len];
459 			isRef = true;
460 			break;
461 
462 		case kOSSerializeNumber:
463 			bufferPos += sizeof(long long);
464 			if (bufferPos > bufferSize) {
465 				break;
466 			}
467 			if ((len != 32) && (len != 64) && (len != 16) && (len != 8)) {
468 				break;
469 			}
470 			value = next[1];
471 			value <<= 32;
472 			value |= next[0];
473 			o = OSNumber::withNumber(value, len);
474 			next += 2;
475 			break;
476 
477 		case kOSSerializeSymbol:
478 			bufferPos += (wordLen * sizeof(uint32_t));
479 			if (bufferPos > bufferSize) {
480 				break;
481 			}
482 			if (len < 2) {
483 				break;
484 			}
485 			if (0 != ((const char *)next)[len - 1]) {
486 				break;
487 			}
488 			o = (OSObject *) OSSymbol::withCString((const char *) next);
489 			next += wordLen;
490 			break;
491 
492 		case kOSSerializeString:
493 			bufferPos += (wordLen * sizeof(uint32_t));
494 			if (bufferPos > bufferSize) {
495 				break;
496 			}
497 			o = OSString::withStringOfLength((const char *) next, len);
498 			next += wordLen;
499 			break;
500 
501 		case kOSSerializeData:
502 			bufferPos += (wordLen * sizeof(uint32_t));
503 			if (bufferPos > bufferSize) {
504 				break;
505 			}
506 			o = OSData::withBytes(next, len);
507 			next += wordLen;
508 			break;
509 
510 		case kOSSerializeBoolean:
511 			o = (len ? kOSBooleanTrue : kOSBooleanFalse);
512 			break;
513 
514 		default:
515 			break;
516 		}
517 
518 		if (!(ok = (o != NULL))) {
519 			break;
520 		}
521 
522 		if (hasLength) {
523 			bufferPos += sizeof(*next);
524 			if (!(ok = (bufferPos <= bufferSize))) {
525 				o->release();
526 				break;
527 			}
528 			length = *next++;
529 		}
530 
531 		if (!isRef) {
532 			setAtIndex(objs, objsIdx, o);
533 			if (!ok) {
534 				o->release();
535 				break;
536 			}
537 			objsIdx++;
538 		}
539 
540 		if (dict) {
541 			if (!sym) {
542 				sym = (OSSymbol *) o;
543 			} else {
544 				str = sym;
545 				sym = OSDynamicCast(OSSymbol, sym);
546 				if (!sym && (str = OSDynamicCast(OSString, str))) {
547 					sym = const_cast<OSSymbol *>(OSSymbol::withString(str));
548 					ok = (sym != NULL);
549 					if (!ok) {
550 						break;
551 					}
552 				}
553 				DEBG("%s = %s\n", sym->getCStringNoCopy(), o->getMetaClass()->getClassName());
554 				if (o != dict) {
555 					ok = dict->setObject(sym, o);
556 				}
557 				if (sym && (sym != str)) {
558 					sym->release();
559 				}
560 				sym = NULL;
561 			}
562 		} else if (array) {
563 			ok = array->setObject(o);
564 		} else if (set) {
565 			ok = set->setObject(o);
566 		} else if (result) {
567 			ok = false;
568 		} else {
569 			assert(!parent);
570 			result = o;
571 		}
572 
573 		if (!ok) {
574 			break;
575 		}
576 
577 		if (end) {
578 			parent = NULL;
579 		}
580 		if (newCollect) {
581 			stackIdx++;
582 			setAtIndex(stack, stackIdx, parent);
583 			if (!ok) {
584 				break;
585 			}
586 			DEBG("++stack[%d] %p\n", stackIdx, parent);
587 			parent = o;
588 			dict   = newDict;
589 			array  = newArray;
590 			set    = newSet;
591 			end    = false;
592 		}
593 
594 		if (end) {
595 			while (stackIdx) {
596 				parent = stackArray[stackIdx];
597 				DEBG("--stack[%d] %p\n", stackIdx, parent);
598 				stackIdx--;
599 				if (parent) {
600 					break;
601 				}
602 			}
603 			if (!parent) {
604 				break;
605 			}
606 			set   = NULL;
607 			dict  = NULL;
608 			array = NULL;
609 			if (!(dict = OSDynamicCast(OSDictionary, parent))) {
610 				if (!(array = OSDynamicCast(OSArray, parent))) {
611 					ok = (NULL != (set = OSDynamicCast(OSSet, parent)));
612 				}
613 			}
614 		}
615 	}
616 	DEBG("ret %p\n", result);
617 
618 	if (!ok) {
619 		result = NULL;
620 	}
621 
622 	if (objsCapacity) {
623 		for (len = (result != NULL); len < objsIdx; len++) {
624 			objsArray[len]->release();
625 		}
626 		kfree(objsArray, objsCapacity  * sizeof(*objsArray));
627 	}
628 	if (stackCapacity) {
629 		kfree(stackArray, stackCapacity * sizeof(*stackArray));
630 	}
631 
632 	return result;
633 }
634 
635 OSObject*
636 OSUnserializeXML(
637 	const char  * buffer,
638 	OSSharedPtr<OSString>& errorString)
639 {
640 	OSString* errorStringRaw = NULL;
641 	OSObject* result = OSUnserializeXML(buffer, &errorStringRaw);
642 	errorString.reset(errorStringRaw, OSNoRetain);
643 	return result;
644 }
645 
646 OSObject*
647 OSUnserializeXML(
648 	const char  * buffer,
649 	size_t        bufferSize,
650 	OSSharedPtr<OSString> &errorString)
651 {
652 	OSString* errorStringRaw = NULL;
653 	OSObject* result = OSUnserializeXML(buffer, bufferSize, &errorStringRaw);
654 	errorString.reset(errorStringRaw, OSNoRetain);
655 	return result;
656 }
657 
658 OSObject*
659 OSUnserializeBinary(const char *buffer, size_t bufferSize, OSSharedPtr<OSString>& errorString)
660 {
661 	OSString* errorStringRaw = NULL;
662 	OSObject* result = OSUnserializeBinary(buffer, bufferSize, &errorStringRaw);
663 	errorString.reset(errorStringRaw, OSNoRetain);
664 	return result;
665 }
666 
667 OSObject*
668 OSUnserialize(const char *buffer, OSSharedPtr<OSString>& errorString)
669 {
670 	OSString* errorStringRaw = NULL;
671 	OSObject* result = OSUnserialize(buffer, &errorStringRaw);
672 	errorString.reset(errorStringRaw, OSNoRetain);
673 	return result;
674 }
675