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++/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 }