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