cdsa/cdsa_utilities/walkers.h

   1 /*
   2  * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved.
   3  *
   4  * The contents of this file constitute Original Code as defined in and are
   5  * subject to the Apple Public Source License Version 1.2 (the 'License').
   6  * You may not use this file except in compliance with the License. Please obtain
   7  * a copy of the License at http://www.apple.com/publicsource and read it before
   8  * using this file.
   9  *
  10  * This Original Code and all software distributed under the License are
  11  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
  12  * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
  13  * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  14  * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
  15  * specific language governing rights and limitations under the License.
  16  */
  17
  18
  19 //
  20 // walkers - facilities for traversing and manipulating recursive data structures
  21 //
  22 // Very briefly, this facility allows for deep traversals of (potentially) recursive
  23 // data structures through templated structure "walkers." Standard operations include
  24 // deep copying to a contiguous memory buffer, size calculation, and reconstitution
  25 // after relocation (e.g. via IPC). You can add other operations (e.g. scattered deep
  26 // copy, debug dumping, etc.) by defining operations classes and applying them to the
  27 // existing walkers. You can also extend the reach of the facility to new data structures
  28 // by writing appropriate walker functions for them.
  29 //
  30 // For more detailed rules and regulations, see the accompanying documentation.
  31 //
  32 #ifndef _H_WALKERS
  33 #define _H_WALKERS
  34
  35 #include <Security/utilities.h>
  36 #include <Security/cssmalloc.h>
  37 #include <Security/memstreams.h>
  38 #include <Security/debugging.h>
  39 #include <set>
  40
  41
  42 namespace Security {
  43 namespace DataWalkers {
  44
  45 #define WALKERDEBUG 1
  46
  47
  48 #if defined(WALKERDEBUG)
  49 # define DEBUGWALK(who) secdebug("walkers", "walk " who " %s@%p (%ld)", \
  50                                                                         Debug::typeName(addr).c_str(), addr, size)
  51 #else
  52 # define DEBUGWALK(who) /* nothing */
  53 #endif
  54
  55
  56 //
  57 // Standard operators for sizing, copying, and reinflating
  58 //
  59 class SizeWalker : public LowLevelMemoryUtilities::Writer::Counter {
  60 public:
  61     template <class T>
  62         void operator () (T &obj, size_t size = sizeof(T)) { }
  63
  64     template <class T>
  65     void operator () (T *addr, size_t size = sizeof(T))
  66     { DEBUGWALK("size"); LowLevelMemoryUtilities::Writer::Counter::insert(size); }
  67
  68         void blob(void *addr, size_t size)
  69         { (*this)(addr, size); }
  70
  71     void reserve(size_t space)
  72     { LowLevelMemoryUtilities::Writer::Counter::insert(space); }
  73
  74     static const bool needsRelinking = false;
  75     static const bool needsSize = true;
  76 };
  77
  78 class CopyWalker : public LowLevelMemoryUtilities::Writer {
  79 public:
  80     CopyWalker() { }
  81     CopyWalker(void *base) : LowLevelMemoryUtilities::Writer(base) { }
  82
  83 public:
  84     template <class T>
  85         void operator () (T &obj, size_t size = sizeof(T))
  86         { }
  87
  88     template <class T>
  89     void operator () (T * &addr, size_t size = sizeof(T))
  90     {
  91                 DEBUGWALK("copy");
  92         if (addr)
  93             addr = reinterpret_cast<T *>(LowLevelMemoryUtilities::Writer::operator () (addr, size));
  94     }
  95
  96         template <class T>
  97         void blob(T * &addr, size_t size)
  98         { (*this)(addr, size); }
  99
 100     static const bool needsRelinking = true;
 101     static const bool needsSize = true;
 102 };
 103
 104 class ReconstituteWalker {
 105 public:
 106     ReconstituteWalker(off_t offset) : mOffset(offset) { }
 107     ReconstituteWalker(void *ptr, void *base)
 108     : mOffset(LowLevelMemoryUtilities::difference(ptr, base)) { }
 109
 110     template <class T>
 111         void operator () (T &obj, size_t size = sizeof(T))
 112         { }
 113
 114     template <class T>
 115     void operator () (T * &addr, size_t size = 0)
 116     {
 117                 DEBUGWALK("reconstitute");
 118         if (addr)
 119             addr = LowLevelMemoryUtilities::increment<T>(addr, mOffset);
 120     }
 121
 122         template <class T>
 123         void blob(T * &addr, size_t size)
 124         { (*this)(addr, size); }
 125
 126     static const bool needsRelinking = true;
 127     static const bool needsSize = false;
 128
 129 private:
 130     off_t mOffset;
 131 };
 132
 133 class ChunkCopyWalker {
 134 public:
 135     ChunkCopyWalker(CssmAllocator &alloc = CssmAllocator::standard()) : allocator(alloc) { }
 136
 137     CssmAllocator &allocator;
 138
 139     template <class T>
 140         void operator () (T &obj, size_t size = sizeof(T))
 141         { }
 142
 143     template <class T>
 144     void operator () (T * &addr, size_t size = sizeof(T))
 145     {
 146                 DEBUGWALK("chunkcopy");
 147 #if BUG_GCC
 148         T *copy = reinterpret_cast<T *>(allocator.malloc(size));
 149 #else
 150         T *copy = allocator.malloc<T>(size);
 151 #endif
 152         memcpy(copy, addr, size);
 153         addr = copy;
 154     }
 155
 156         template <class T>
 157         void blob(T * &addr, size_t size)
 158         { (*this)(addr, size); }
 159
 160     static const bool needsRelinking = true;
 161     static const bool needsSize = true;
 162 };
 163
 164 class ChunkFreeWalker {
 165 public:
 166     ChunkFreeWalker(CssmAllocator &alloc = CssmAllocator::standard()) : allocator(alloc) { }
 167
 168     CssmAllocator &allocator;
 169
 170     template <class T>
 171         void operator () (T &obj, size_t size = 0)
 172         { }
 173
 174         template <class T>
 175     void operator () (T *addr, size_t size = 0)
 176     {
 177                 DEBUGWALK("chunkfree");
 178         freeSet.insert(addr);
 179     }
 180
 181         void blob(void *addr, size_t size)
 182         { (*this)(addr, 0); }
 183
 184     void free();
 185     ~ChunkFreeWalker() { free(); }
 186
 187     static const bool needsRelinking = false;
 188     static const bool needsSize = false;
 189
 190 private:
 191     std::set<void *> freeSet;
 192 };
 193
 194
 195 //
 196 // Stand-alone operations for a single structure web
 197 //
 198 template <class T>
 199 size_t size(T obj)
 200 {
 201     SizeWalker w;
 202     walk(w, obj);
 203     return w;
 204 }
 205
 206
 207 template <class T>
 208 T *copy(const T *obj, void *addr)
 209 {
 210     if (obj == NULL)
 211         return NULL;
 212     CopyWalker w(addr);
 213     walk(w, obj);
 214     return reinterpret_cast<T *>(addr);
 215 }
 216
 217 template <class T>
 218 T *copy(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 219 {
 220     return obj ? copy(obj, alloc, size(obj)) : NULL;
 221 }
 222
 223 template <class T>
 224 T *copy(const T *obj, CssmAllocator &alloc, size_t size)
 225 {
 226     if (obj == NULL)
 227         return NULL;
 228     return copy(obj, alloc.malloc(size));
 229 }
 230
 231 template <class T>
 232 void copy(const T *obj, CssmAllocator &alloc, CssmData &data)
 233 {
 234     if (obj == NULL) {
 235         data.Length = 0;
 236         return;
 237     }
 238     if (data.data() == NULL) {
 239         size_t length = size(obj);
 240         data = CssmData(alloc.malloc(length), length);
 241     } else
 242         assert(size(obj) <= data.length());
 243     copy(obj, data.data());
 244 }
 245
 246
 247 template <class T>
 248 void relocate(T *obj, T *base)
 249 {
 250         if (obj) {
 251                 ReconstituteWalker w(LowLevelMemoryUtilities::difference(obj, base));
 252                 walk(w, base);
 253         }
 254 }
 255
 256
 257 template <class T>
 258 T *chunkCopy(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 259 {
 260         if (obj) {
 261                 ChunkCopyWalker w(alloc);
 262                 return walk(w, obj);
 263         } else
 264                 return NULL;
 265 }
 266
 267 template <class T>
 268 void chunkFree(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 269 {
 270     if (obj) {
 271                 ChunkFreeWalker w(alloc);
 272                 walk(w, obj);
 273         }
 274 }
 275
 276 template <class T>
 277 class Copier {
 278 public:
 279     Copier(const T *obj, CssmAllocator &alloc = CssmAllocator::standard()) : allocator(alloc)
 280     {
 281         if (obj == NULL) {
 282             mValue = NULL;
 283             mLength = 0;
 284         } else {
 285             mLength = size(obj);
 286 #if BUG_GCC
 287             mValue = reinterpret_cast<T *>(alloc.malloc(mLength));
 288 #else
 289             mValue = alloc.malloc<T>(mLength);
 290 #endif
 291             mValue = copy(obj, mValue);
 292         }
 293     }
 294
 295     Copier(const T *obj, uint32 count, CssmAllocator &alloc = CssmAllocator::standard())
 296                 : allocator(alloc)
 297     {
 298         if (obj == NULL) {
 299             mValue = NULL;
 300             mLength = 0;
 301         } else {
 302             SizeWalker sizer;
 303             sizer.reserve(sizeof(T) * count);   // initial vector size
 304             for (uint32 n = 0; n < count; n++)
 305                 walk(sizer, obj[n]);    // dependent data sizes
 306             mLength = sizer;
 307 #if BUG_GCC
 308             mValue = reinterpret_cast<T *>(alloc.malloc(mLength));
 309 #else
 310             mValue = alloc.malloc<T>(mLength);
 311 #endif
 312             CopyWalker copier(LowLevelMemoryUtilities::increment(mValue, sizeof(T) * count));
 313             for (uint32 n = 0; n < count; n++) {
 314                 mValue[n] = obj[n];
 315                 walk(copier, mValue[n]);
 316             }
 317         }
 318     }
 319
 320     CssmAllocator &allocator;
 321
 322     ~Copier() { allocator.free(mValue); }
 323
 324         T *value() const                { return mValue; }
 325     operator T *() const        { return value(); }
 326     size_t length() const       { return mLength; }
 327
 328     T *keep() { T *result = mValue; mValue = NULL; return result; }
 329
 330 private:
 331     T *mValue;
 332     size_t mLength;
 333 };
 334
 335
 336 //
 337 // Allow const pointer input but cast the const-ness away.
 338 // This is valid because the walkers never directly *write* into *obj;
 339 // they just pass their parts along to operate(). If we are in a writing
 340 // pass, operate() must ensure it copies (and replaces) its argument to
 341 // make it writable.
 342 // (The alternative design calls for three walk() functions for each type,
 343 //  which is ugly and error prone.)
 344 //
 345 template <class Action, class T>
 346 T *walk(Action &operate, const T * &obj)
 347 { return walk(operate, const_cast<T * &>(obj)); }
 348
 349
 350 //
 351 // The generic default walkers assume no structure, i.e. no recursive walks
 352 //
 353 template <class Action, class Type>
 354 void walk(Action &operate, Type &obj)
 355 {
 356     operate(obj);
 357 }
 358
 359 template <class Action, class Type>
 360 Type *walk(Action &operate, Type * &obj)
 361 {
 362     operate(obj);
 363     return obj;
 364 }
 365
 366
 367 } // end namespace DataWalkers
 368 } // end namespace Security
 369
 370 #endif //_H_WALKERS