libkern/c++/OSSerializeBinary.cpp

   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 }