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/memutils.h>
  38 #include <set>
  39
  40 #ifdef _CPP_WALKERS
  41 # pragma export on
  42 #endif
  43
  44
  45 namespace Security
  46 {
  47
  48 namespace DataWalkers
  49 {
  50
  51 //
  52 // Standard operators for sizing, copying, and reinflating
  53 //
  54 class SizeWalker : public LowLevelMemoryUtilities::Writer::Counter {
  55 public:
  56     template <class T>
  57     void operator () (T *, size_t size = sizeof(T))
  58     { LowLevelMemoryUtilities::Writer::Counter::insert(size); }
  59
  60     void reserve(size_t space)
  61     { LowLevelMemoryUtilities::Writer::Counter::insert(space); }
  62
  63     static const bool needsRelinking = false;
  64     static const bool needsSize = true;
  65 };
  66
  67 class CopyWalker : public LowLevelMemoryUtilities::Writer {
  68 public:
  69     CopyWalker() { }
  70     CopyWalker(void *base) : LowLevelMemoryUtilities::Writer(base) { }
  71
  72     template <class T>
  73     void operator () (T * &addr, size_t size = sizeof(T))
  74     {
  75         if (addr)
  76             addr = reinterpret_cast<T *>(LowLevelMemoryUtilities::Writer::operator () (addr, size));
  77     }
  78
  79     static const bool needsRelinking = true;
  80     static const bool needsSize = true;
  81 };
  82
  83 class ReconstituteWalker {
  84 public:
  85     ReconstituteWalker(off_t offset) : mOffset(offset) { }
  86     ReconstituteWalker(void *ptr, void *base)
  87     : mOffset(LowLevelMemoryUtilities::difference(ptr, base)) { }
  88
  89     template <class T>
  90     void operator () (T * &addr, size_t = 0)
  91     {
  92         if (addr)
  93             addr = LowLevelMemoryUtilities::increment<T>(addr, mOffset);
  94     }
  95
  96     static const bool needsRelinking = true;
  97     static const bool needsSize = false;
  98
  99 private:
 100     off_t mOffset;
 101 };
 102
 103 class ChunkCopyWalker {
 104 public:
 105     ChunkCopyWalker(CssmAllocator &alloc = CssmAllocator::standard()) : allocator(alloc) { }
 106
 107     CssmAllocator &allocator;
 108
 109     template <class T>
 110     void operator () (T * &addr, size_t size = sizeof(T))
 111     {
 112 #if BUG_GCC
 113         T *copy = reinterpret_cast<T *>(allocator.malloc(size));
 114 #else
 115         T *copy = allocator.malloc<T>(size);
 116 #endif
 117         memcpy(copy, addr, size);
 118         addr = copy;
 119     }
 120
 121     static const bool needsRelinking = true;
 122     static const bool needsSize = true;
 123 };
 124
 125 class ChunkFreeWalker {
 126 public:
 127     ChunkFreeWalker(CssmAllocator &alloc = CssmAllocator::standard()) : allocator(alloc) { }
 128
 129     CssmAllocator &allocator;
 130
 131     template <class T>
 132     void operator () (T *addr, size_t = sizeof(T))
 133     {
 134         freeSet.insert(addr);
 135     }
 136
 137     void free();
 138     ~ChunkFreeWalker() { free(); }
 139
 140     static const bool needsRelinking = false;
 141     static const bool needsSize = false;
 142
 143 private:
 144     set<void *> freeSet;
 145 };
 146
 147
 148 //
 149 // The VirtualWalker class is a generic walker interface
 150 // for dynamic passing around.
 151 //
 152 class VirtualWalker {
 153 public:
 154     VirtualWalker(bool nrl = false) : needsRelinking(nrl) { }
 155     virtual ~VirtualWalker();
 156
 157     virtual void operator () (void * &addr, size_t size) = 0;
 158
 159     const bool needsRelinking;
 160 };
 161
 162 template <class Walker>
 163 class VirtualWalkerFor : public VirtualWalker {
 164 public:
 165     VirtualWalkerFor(Walker &w, bool nrl = false) : VirtualWalker(nrl), walker(w) { }
 166     void operator () (void * &addr, size_t size)
 167     { walker(addr, size); }
 168
 169     Walker &walker;
 170 };
 171
 172
 173 //
 174 // Stand-alone operations for a single structure web
 175 //
 176 template <class T>
 177 size_t size(T obj)
 178 {
 179     SizeWalker w;
 180     walk(w, obj);
 181     return w;
 182 }
 183
 184 template <class T>
 185 T *copy(const T *obj, void *addr)
 186 {
 187     if (obj == NULL)
 188         return NULL;
 189     CopyWalker w(addr);
 190     walk(w, obj);
 191     return reinterpret_cast<T *>(addr);
 192 }
 193
 194 template <class T>
 195 T *copy(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 196 {
 197     return obj ? copy(obj, alloc, size(obj)) : NULL;
 198 }
 199
 200 template <class T>
 201 T *copy(const T *obj, CssmAllocator &alloc, size_t size)
 202 {
 203     if (obj == NULL)
 204         return NULL;
 205     return copy(obj, alloc.malloc(size));
 206 }
 207
 208 template <class T>
 209 void relocate(T *obj, T *base)
 210 {
 211         if (obj) {
 212                 ReconstituteWalker w(LowLevelMemoryUtilities::difference(obj, base));
 213                 walk(w, base);
 214         }
 215 }
 216
 217 template <class T>
 218 T *chunkCopy(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 219 {
 220         if (obj) {
 221                 ChunkCopyWalker w(alloc);
 222                 return walk(w, obj);
 223         } else
 224                 return NULL;
 225 }
 226
 227 template <class T>
 228 void chunkFree(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 229 {
 230     if (obj) {
 231                 ChunkFreeWalker w(alloc);
 232                 walk(w, obj);
 233         }
 234 }
 235
 236 template <class T>
 237 class Copier {
 238 public:
 239     Copier(const T *obj, CssmAllocator &alloc = CssmAllocator::standard()) : allocator(alloc)
 240     {
 241         if (obj == NULL) {
 242             mValue = NULL;
 243             mLength = 0;
 244         } else {
 245             mLength = size(obj);
 246 #if BUG_GCC
 247             mValue = reinterpret_cast<T *>(alloc.malloc(mLength));
 248 #else
 249             mValue = alloc.malloc<T>(mLength);
 250 #endif
 251             mValue = copy(obj, mValue);
 252         }
 253     }
 254
 255     Copier(const T *obj, uint32 count, CssmAllocator &alloc = CssmAllocator::standard())
 256                 : allocator(alloc)
 257     {
 258         if (obj == NULL) {
 259             mValue = NULL;
 260             mLength = 0;
 261         } else {
 262             SizeWalker sizer;
 263             sizer.reserve(sizeof(T) * count);   // initial vector size
 264             for (uint32 n = 0; n < count; n++)
 265                 walk(sizer, obj[n]);    // dependent data sizes
 266             mLength = sizer;
 267 #if BUG_GCC
 268             mValue = reinterpret_cast<T *>(alloc.malloc(mLength));
 269 #else
 270             mValue = alloc.malloc<T>(mLength);
 271 #endif
 272             CopyWalker copier(LowLevelMemoryUtilities::increment(mValue, sizeof(T) * count));
 273             for (uint32 n = 0; n < count; n++) {
 274                 mValue[n] = obj[n];
 275                 walk(copier, mValue[n]);
 276             }
 277         }
 278     }
 279
 280     CssmAllocator &allocator;
 281
 282     ~Copier() { allocator.free(mValue); }
 283
 284     operator T *() const { return mValue; }
 285     size_t length() const { return mLength; }
 286
 287     T *keep() { T *result = mValue; mValue = NULL; return result; }
 288
 289 private:
 290     T *mValue;
 291     size_t mLength;
 292 };
 293
 294
 295 //
 296 // Allow const pointer input but cast the const-ness away.
 297 // This is valid because the walkers never directly *write* into *obj;
 298 // they just pass their parts along to operate(). If we are in a writing
 299 // pass, operate() must ensure it copies (and replaces) its argument to
 300 // make it writable.
 301 // (The alternative design calls for three walk() functions for each type,
 302 //  which is ugly and error prone.)
 303 //
 304 template <class Action, class T>
 305 T *walk(Action &operate, const T * &obj)
 306 { return walk(operate, const_cast<T * &>(obj)); }
 307
 308
 309 //
 310 // The default walker assumes a flat data structure
 311 //
 312 template <class Action, class Type>
 313 Type *walk(Action &operate, Type * &obj)
 314 {
 315     operate(obj);
 316     return obj;
 317 }
 318
 319
 320 } // end namespace DataWalkers
 321
 322 } // end namespace Security
 323
 324 #ifdef _CPP_WALKERS
 325 # pragma export off
 326 #endif
 327
 328 #endif //_H_WALKERS