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     std::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
 185 template <class T>
 186 T *copy(const T *obj, void *addr)
 187 {
 188     if (obj == NULL)
 189         return NULL;
 190     CopyWalker w(addr);
 191     walk(w, obj);
 192     return reinterpret_cast<T *>(addr);
 193 }
 194
 195 template <class T>
 196 T *copy(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 197 {
 198     return obj ? copy(obj, alloc, size(obj)) : NULL;
 199 }
 200
 201 template <class T>
 202 T *copy(const T *obj, CssmAllocator &alloc, size_t size)
 203 {
 204     if (obj == NULL)
 205         return NULL;
 206     return copy(obj, alloc.malloc(size));
 207 }
 208
 209 template <class T>
 210 void copy(const T *obj, CssmAllocator &alloc, CssmData &data)
 211 {
 212     if (obj == NULL) {
 213         data.Length = 0;
 214         return;
 215     }
 216     if (data.data() == NULL) {
 217         size_t length = size(obj);
 218         data = CssmData(alloc.malloc(length), length);
 219     } else
 220         assert(size(obj) <= data.length());
 221     copy(obj, data.data());
 222 }
 223
 224
 225 template <class T>
 226 void relocate(T *obj, T *base)
 227 {
 228         if (obj) {
 229                 ReconstituteWalker w(LowLevelMemoryUtilities::difference(obj, base));
 230                 walk(w, base);
 231         }
 232 }
 233
 234
 235 template <class T>
 236 T *chunkCopy(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 237 {
 238         if (obj) {
 239                 ChunkCopyWalker w(alloc);
 240                 return walk(w, obj);
 241         } else
 242                 return NULL;
 243 }
 244
 245 template <class T>
 246 void chunkFree(const T *obj, CssmAllocator &alloc = CssmAllocator::standard())
 247 {
 248     if (obj) {
 249                 ChunkFreeWalker w(alloc);
 250                 walk(w, obj);
 251         }
 252 }
 253
 254 template <class T>
 255 class Copier {
 256 public:
 257     Copier(const T *obj, CssmAllocator &alloc = CssmAllocator::standard()) : allocator(alloc)
 258     {
 259         if (obj == NULL) {
 260             mValue = NULL;
 261             mLength = 0;
 262         } else {
 263             mLength = size(obj);
 264 #if BUG_GCC
 265             mValue = reinterpret_cast<T *>(alloc.malloc(mLength));
 266 #else
 267             mValue = alloc.malloc<T>(mLength);
 268 #endif
 269             mValue = copy(obj, mValue);
 270         }
 271     }
 272
 273     Copier(const T *obj, uint32 count, CssmAllocator &alloc = CssmAllocator::standard())
 274                 : allocator(alloc)
 275     {
 276         if (obj == NULL) {
 277             mValue = NULL;
 278             mLength = 0;
 279         } else {
 280             SizeWalker sizer;
 281             sizer.reserve(sizeof(T) * count);   // initial vector size
 282             for (uint32 n = 0; n < count; n++)
 283                 walk(sizer, obj[n]);    // dependent data sizes
 284             mLength = sizer;
 285 #if BUG_GCC
 286             mValue = reinterpret_cast<T *>(alloc.malloc(mLength));
 287 #else
 288             mValue = alloc.malloc<T>(mLength);
 289 #endif
 290             CopyWalker copier(LowLevelMemoryUtilities::increment(mValue, sizeof(T) * count));
 291             for (uint32 n = 0; n < count; n++) {
 292                 mValue[n] = obj[n];
 293                 walk(copier, mValue[n]);
 294             }
 295         }
 296     }
 297
 298     CssmAllocator &allocator;
 299
 300     ~Copier() { allocator.free(mValue); }
 301
 302     operator T *() const { return mValue; }
 303     size_t length() const { return mLength; }
 304
 305     T *keep() { T *result = mValue; mValue = NULL; return result; }
 306
 307 private:
 308     T *mValue;
 309     size_t mLength;
 310 };
 311
 312
 313 //
 314 // Allow const pointer input but cast the const-ness away.
 315 // This is valid because the walkers never directly *write* into *obj;
 316 // they just pass their parts along to operate(). If we are in a writing
 317 // pass, operate() must ensure it copies (and replaces) its argument to
 318 // make it writable.
 319 // (The alternative design calls for three walk() functions for each type,
 320 //  which is ugly and error prone.)
 321 //
 322 template <class Action, class T>
 323 T *walk(Action &operate, const T * &obj)
 324 { return walk(operate, const_cast<T * &>(obj)); }
 325
 326
 327 //
 328 // The default walker assumes a flat data structure
 329 //
 330 template <class Action, class Type>
 331 Type *walk(Action &operate, Type * &obj)
 332 {
 333     operate(obj);
 334     return obj;
 335 }
 336
 337
 338 } // end namespace DataWalkers
 339
 340 } // end namespace Security
 341
 342 #ifdef _CPP_WALKERS
 343 # pragma export off
 344 #endif
 345
 346 #endif //_H_WALKERS