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