OSX/libsecurity_utilities/lib/superblob.h

   1 //
   2 // SuperBlob - a typed bag of Blobs
   3 //
   4 #ifndef _H_SUPERBLOB
   5 #define _H_SUPERBLOB
   6
   7 #include <security_utilities/blob.h>
   8 #include <map>
   9 #include <vector>
  10
  11 namespace Security {
  12
  13
  14 //
  15 // A SuperBlob is a Blob that contains multiple sub-Blobs of varying type.
  16 // The SuperBlob is contiguous and contains a directory of its sub-blobs.
  17 // A Maker is included.
  18 //
  19 // SuperBlobCore lets you define your own SuperBlob type. To just use a generic
  20 // SuperBlob, use SuperBlob<> below.
  21 //
  22 template <class _BlobType, uint32_t _magic, class _Type>
  23 class SuperBlobCore: public Blob<_BlobType, _magic> {
  24 public:
  25         class Maker; friend class Maker;
  26
  27         typedef _Type Type;
  28
  29         // echoes from parent BlobCore (the C++ type system is too restrictive here)
  30         typedef BlobCore::Offset Offset;
  31         template <class BlobType> BlobType *at(Offset offset) { return BlobCore::at<BlobType>(offset); }
  32         template <class BlobType> const BlobType *at(Offset offset) const { return BlobCore::at<BlobType>(offset); }
  33
  34         void setup(size_t size, unsigned count)
  35         { this->initialize(size); this->mCount = count; }
  36
  37         struct Index {
  38                 Endian<Type> type;                      // type of sub-Blob
  39                 Endian<Offset> offset;          // starting offset
  40         };
  41
  42         bool validateBlob(size_t maxSize = 0) const;
  43         bool strictValidateBlob(size_t maxSize = 0) const;
  44
  45         unsigned count() const { return mCount; }
  46
  47         // access by index number
  48         Type type(unsigned n) const { assert(n < mCount); return mIndex[n].type; }
  49         const BlobCore *blob(unsigned n) const
  50                 { assert(n < mCount); return mIndex[n].offset ? at<const BlobCore>(mIndex[n].offset) : NULL; }
  51         template <class BlobType>
  52         const BlobType *blob(unsigned n) const { return BlobType::specific(blob(n)); }
  53
  54         // access by index type (assumes unique types)
  55         const BlobCore *find(Type type) const;
  56         template <class BlobType>
  57         const BlobType *find(Type type) const { return BlobType::specific(find(type)); }
  58
  59 private:
  60         Endian<uint32_t> mCount;                // number of sub-Blobs following
  61         Index mIndex[0];                                // <count> IndexSlot structures
  62         // followed by sub-Blobs, packed and ordered in an undefined way
  63 };
  64
  65
  66 template <class _BlobType, uint32_t _magic, class _Type>
  67 inline bool SuperBlobCore<_BlobType, _magic, _Type>::validateBlob(size_t maxSize /* = 0 */) const
  68 {
  69         unsigned count = mCount;
  70         size_t ixLimit = sizeof(SuperBlobCore) + count * sizeof(Index); // end of index vector
  71         if (!BlobCore::validateBlob(_magic, ixLimit, maxSize))
  72                 return false;
  73         for (const Index *ix = mIndex + count - 1; ix >= mIndex; ix--) {
  74                 Offset offset = ix->offset;
  75                 if (offset)                                                                                                                                             // if non-null
  76                         if (offset < ixLimit                                                                                                            // offset not too small
  77                                 || offset + sizeof(BlobCore) > this->length()                                                   // fits Blob header (including length field)
  78                                 || offset + at<const BlobCore>(offset)->length() > this->length())      // fits entire blob
  79                                 return false;
  80         }
  81         return true;
  82 }
  83
  84 struct _SBRange {
  85         size_t base;
  86         size_t end;
  87         _SBRange(size_t b, size_t len) : base(b), end(b+len) { }
  88         bool operator < (const _SBRange& other) const { return this->base < other.base; }
  89 };
  90
  91 template <class _BlobType, uint32_t _magic, class _Type>
  92 inline bool SuperBlobCore<_BlobType, _magic, _Type>::strictValidateBlob(size_t size /* = 0 */) const
  93 {
  94         if (!validateBlob(size))        // verifies in-bound sub-blobs
  95                 return false;
  96         unsigned count = mCount;
  97         if (count == 0)
  98                 return this->length() == sizeof(SuperBlobCore); // nothing in here
  99
 100         std::vector<_SBRange> ranges;
 101         for (unsigned ix = 0; ix < count; ++ix)
 102                 ranges.push_back(_SBRange(mIndex[ix].offset, this->blob(ix)->length()));
 103         sort(ranges.begin(), ranges.end());
 104         if (ranges[0].base != sizeof(SuperBlobCore) + count * sizeof(Index))
 105                 return false;   // start anchor
 106         for (unsigned ix = 1; ix < count; ++ix)
 107                 if (ranges[ix].base != ranges[ix-1].end)        // nothing in between
 108                         return false;
 109         return ranges[count-1].end == this->length();   // end anchor
 110 }
 111
 112
 113 //
 114 // A generic SuperBlob ready for use. You still need to specify a magic number.
 115 //
 116 template <uint32_t _magic, class _Type = uint32_t>
 117 class SuperBlob : public SuperBlobCore<SuperBlob<_magic, _Type>, _magic, _Type> {
 118 };
 119
 120
 121 template <class _BlobType, uint32_t _magic, class _Type>
 122 const BlobCore *SuperBlobCore<_BlobType, _magic, _Type>::find(Type type) const
 123 {
 124         for (unsigned slot = 0; slot < mCount; slot++)
 125                 if (mIndex[slot].type == type)
 126                         return mIndex[slot].offset ? at<const BlobCore>(mIndex[slot].offset) : NULL;
 127         return NULL;    // not found
 128 }
 129
 130
 131 //
 132 // A SuperBlob::Maker simply assembles multiple Blobs into a single, indexed
 133 // super-blob. Just add() sub-Blobs by type and call make() to get
 134 // the result, malloc'ed. A Maker is not resettable.
 135 // Maker can repeatedly make SuperBlobs from the same (cached) inputs.
 136 // It can also tell you how big its output will be, given established contents
 137 // plus (optional) additional sizes of blobs yet to come.
 138 //
 139 template <class _BlobType, uint32_t _magic, class _Type>
 140 class SuperBlobCore<_BlobType, _magic, _Type>::Maker {
 141 public:
 142         Maker() { }
 143
 144         Maker(const Maker &src)
 145         {
 146                 for (typename BlobMap::iterator it = mPieces.begin(); it != mPieces.end(); ++it)
 147                         mPieces.insert(make_pair(it->first, it->second->clone()));
 148         }
 149
 150         ~Maker()
 151         {
 152                 for (typename BlobMap::iterator it = mPieces.begin(); it != mPieces.end(); ++it)
 153                         ::free(it->second);
 154         }
 155
 156         void add(Type type, BlobCore *blob);            // takes ownership of blob
 157         void add(const _BlobType *blobs);                       // copies all blobs
 158         void add(const Maker &maker);                           // ditto
 159
 160         bool contains(Type type) const                          // see if we have this type already
 161                 { return mPieces.find(type) != mPieces.end(); }
 162         BlobCore *get(Type type) const
 163                 {
 164                         typename BlobMap::const_iterator it = mPieces.find(type);
 165                         return (it == mPieces.end()) ? NULL : it->second;
 166                 }
 167
 168 //      size_t size(size_t size1 = 0, ...) const;       // size with optional additional blob sizes
 169         size_t size(const std::vector<size_t> &sizes, size_t size1 = 0, ...) const; // same with array-of-sizes input
 170         _BlobType *make() const;                                        // create (malloc) and return SuperBlob
 171         _BlobType *operator () () const { return make(); }
 172
 173 private:
 174         typedef std::map<Type, BlobCore *> BlobMap;
 175         BlobMap mPieces;
 176 };
 177
 178
 179 //
 180 // Add a Blob to a SuperBlob::Maker.
 181 // This takes ownership of the blob, which must have been malloc'ed.
 182 // Any previous value set for this Type will be freed immediately.
 183 //
 184 template <class _BlobType, uint32_t _magic, class _Type>
 185 void SuperBlobCore<_BlobType, _magic, _Type>::Maker::add(Type type, BlobCore *blob)
 186 {
 187         pair<typename BlobMap::iterator, bool> r = mPieces.insert(make_pair(type, blob));
 188         if (!r.second) {        // already there
 189                 secinfo("superblob", "Maker %p replaces type=%d", this, type);
 190                 ::free(r.first->second);
 191                 r.first->second = blob;
 192         }
 193 }
 194
 195 template <class _BlobType, uint32_t _magic, class _Type>
 196 void SuperBlobCore<_BlobType, _magic, _Type>::Maker::add(const _BlobType *blobs)
 197 {
 198         for (uint32_t ix = 0; ix < blobs->mCount; ix++)
 199                 this->add(blobs->mIndex[ix].type, blobs->blob(ix)->clone());
 200 }
 201
 202 template <class _BlobType, uint32_t _magic, class _Type>
 203 void SuperBlobCore<_BlobType, _magic, _Type>::Maker::add(const Maker &maker)
 204 {
 205         for (typename BlobMap::const_iterator it = maker.mPieces.begin(); it != maker.mPieces.end(); ++it)
 206                 this->add(it->first, it->second->clone());
 207 }
 208
 209
 210 //
 211 // Calculate the size the new SuperBlob would have, given the contents of the Maker
 212 // so far, plus additional blobs with the sizes given.
 213 //
 214 template <class _BlobType, uint32_t _magic, class _Type>
 215 size_t SuperBlobCore<_BlobType, _magic, _Type>::Maker::size(const std::vector<size_t> &sizes, size_t size1, ...) const
 216 {
 217         // count established blobs
 218         size_t count = mPieces.size();
 219         size_t total = 0;
 220         for (auto it = mPieces.begin(); it != mPieces.end(); ++it)
 221                 total += it->second->length();
 222
 223         // add more blobs from the sizes array
 224         for (auto it = sizes.begin(); it != sizes.end(); ++it)
 225                 total += *it;
 226         count += sizes.size();
 227
 228         // add more blobs from individual sizes specified
 229         if (size1) {
 230                 va_list args;
 231                 va_start(args, size1);
 232                 do {
 233                         count++;
 234                         total += size1;
 235                         size1 = va_arg(args, size_t);
 236                 } while (size1);
 237                 va_end(args);
 238         }
 239
 240         return sizeof(SuperBlobCore) + count * sizeof(Index) + total;
 241 }
 242
 243
 244 //
 245 // Finish SuperBlob construction and return the new, malloc'ed, SuperBlob.
 246 // This can be done repeatedly.
 247 //
 248 template <class _BlobType, uint32_t _magic, class _Type>
 249 _BlobType *SuperBlobCore<_BlobType, _magic, _Type>::Maker::make() const
 250 {
 251         Offset pc = (Offset)(sizeof(SuperBlobCore) + mPieces.size() * sizeof(Index));
 252         Offset total = (Offset)size(vector<size_t>(), 0);
 253         _BlobType *result = (_BlobType *)malloc(total);
 254         if (!result)
 255                 UnixError::throwMe(ENOMEM);
 256         result->setup(total, (unsigned)mPieces.size());
 257         unsigned n = 0;
 258         for (typename BlobMap::const_iterator it = mPieces.begin(); it != mPieces.end(); ++it) {
 259                 result->mIndex[n].type = it->first;
 260                 result->mIndex[n].offset = pc;
 261                 memcpy(result->template at<unsigned char>(pc), it->second, it->second->length());
 262                 pc += it->second->length();
 263                 n++;
 264         }
 265         secinfo("superblob", "Maker %p assembles %ld blob(s) into %p (size=%d)",
 266                 this, mPieces.size(), result, total);
 267         return result;
 268 }
 269
 270
 271 }       // Security
 272
 273 #endif //_H_SUPERBLOB