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