1/* 2 * Copyright (c) 2000-2006 Apple Computer, Inc. All Rights Reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24 25// 26// walkers - facilities for traversing and manipulating recursive data structures 27// 28// Very briefly, this facility allows for deep traversals of (potentially) recursive 29// data structures through templated structure "walkers." Standard operations include 30// deep copying to a contiguous memory buffer, size calculation, deep freeing, reconstitution 31// after relocation (e.g. via IPC), and others. You can add other operations (e.g. scattered deep 32// copy, debug dumping, etc.) by defining operations classes and applying them to the 33// existing walkers. You can also extend the reach of the facility to new data structures 34// by writing appropriate walker functions for them. 35// 36// NOTE: We no longer have a default walker for flat structures. You must define 37// a walk(operate, foo * &) function for every data type encountered during a walk 38// or you will get compile-time errors. 39// 40// For more detailed rules and regulations, see the accompanying documentation. 41// 42#ifndef _H_WALKERS 43#define _H_WALKERS 44 45#include <security_utilities/alloc.h> 46#include <security_utilities/memstreams.h> 47#include <security_cdsa_utilities/cssmdata.h> 48#include <security_utilities/debugging.h> 49#include <set> 50 51 52namespace Security { 53namespace DataWalkers { 54 55#define WALKERDEBUG 0 56 57 58#if WALKERDEBUG 59# define DEBUGWALK(who) secdebug("walkers", "walk " who " %s@%p (%ld)", \ 60 Debug::typeName(addr).c_str(), addr, size) 61#else 62# define DEBUGWALK(who) /* nothing */ 63#endif 64 65 66// 67// SizeWalker simply walks a structure and calculates how many bytes 68// CopyWalker would use to make a flat copy. This is naturally at least 69// the sum of all relevant sizes, but can be more due to alignment and 70// counting overhead. 71// 72class SizeWalker : public LowLevelMemoryUtilities::Writer::Counter { 73public: 74 template <class T> 75 void operator () (T &obj, size_t size = sizeof(T)) { } 76 77 template <class T> 78 void operator () (T *addr, size_t size = sizeof(T)) 79 { DEBUGWALK("size"); LowLevelMemoryUtilities::Writer::Counter::insert(size); } 80 81 void blob(void *addr, size_t size) 82 { (*this)(addr, size); } 83 84 void reserve(size_t space) 85 { LowLevelMemoryUtilities::Writer::Counter::insert(space); } 86 87 static const bool needsRelinking = false; 88 static const bool needsSize = true; 89}; 90 91 92// 93// CopyWalker makes a deep, flat copy of a structure. The result will work 94// just like the original (with all elements recursively copied), except that 95// it occupies contiguous memory. 96// 97class CopyWalker : public LowLevelMemoryUtilities::Writer { 98public: 99 CopyWalker() { } 100 CopyWalker(void *base) : LowLevelMemoryUtilities::Writer(base) { } 101 102public: 103 template <class T> 104 void operator () (T &obj, size_t size = sizeof(T)) 105 { } 106 107 template <class T> 108 void operator () (T * &addr, size_t size = sizeof(T)) 109 { 110 DEBUGWALK("copy"); 111 if (addr) 112 addr = reinterpret_cast<T *>(LowLevelMemoryUtilities::Writer::operator () (addr, size)); 113 } 114 115 template <class T> 116 void blob(T * &addr, size_t size) 117 { (*this)(addr, size); } 118 119 static const bool needsRelinking = true; 120 static const bool needsSize = true; 121}; 122 123 124// 125// Walk a structure and apply a constant linear shift to all pointers 126// encountered. This is useful when a structure and its deep components 127// have been linearly shifted by something (say, an IPC transit). 128// 129class ReconstituteWalker { 130public: 131 ReconstituteWalker(off_t offset) : mOffset(offset) { } 132 ReconstituteWalker(void *ptr, void *base) 133 : mOffset(LowLevelMemoryUtilities::difference(ptr, base)) { } 134 135 template <class T> 136 void operator () (T &obj, size_t size = sizeof(T)) 137 { } 138 139 template <class T> 140 void operator () (T * &addr, size_t size = 0) 141 { 142 DEBUGWALK("reconstitute"); 143 if (addr) 144 addr = LowLevelMemoryUtilities::increment<T>(addr, (ptrdiff_t)mOffset); 145 } 146 147 template <class T> 148 void blob(T * &addr, size_t size) 149 { (*this)(addr, size); } 150 151 static const bool needsRelinking = true; 152 static const bool needsSize = false; 153 154private: 155 off_t mOffset; 156}; 157 158 159// 160// Make an element-by-element copy of a structure. Each pointer followed 161// uses a separate allocation for its pointed-to storage. 162// 163class ChunkCopyWalker { 164public: 165 ChunkCopyWalker(Allocator &alloc = Allocator::standard()) : allocator(alloc) { } 166 167 Allocator &allocator; 168 169 template <class T> 170 void operator () (T &obj, size_t size = sizeof(T)) 171 { } 172 173 template <class T> 174 void operator () (T * &addr, size_t size = sizeof(T)) 175 { 176 DEBUGWALK("chunkcopy"); 177#if BUG_GCC 178 T *copy = reinterpret_cast<T *>(allocator.malloc(size)); 179#else 180 T *copy = allocator.malloc<T>(size); 181#endif 182 memcpy(copy, addr, size); 183 addr = copy; 184 } 185 186 template <class T> 187 void blob(T * &addr, size_t size) 188 { (*this)(addr, size); } 189 190 static const bool needsRelinking = true; 191 static const bool needsSize = true; 192}; 193 194 195// 196// Walk a structure and call an Allocator to separate free each node. 197// This is safe for non-trees (i.e. shared subsidiary nodes); such will 198// only be freed once. 199// 200class ChunkFreeWalker { 201public: 202 ChunkFreeWalker(Allocator &alloc = Allocator::standard()) : allocator(alloc) { } 203 204 Allocator &allocator; 205 206 template <class T> 207 void operator () (T &obj, size_t size = 0) 208 { } 209 210 template <class T> 211 void operator () (T *addr, size_t size = 0) 212 { 213 DEBUGWALK("chunkfree"); 214 freeSet.insert(addr); 215 } 216 217 void blob(void *addr, size_t size) 218 { (*this)(addr, 0); } 219 220 void free(); 221 ~ChunkFreeWalker() { free(); } 222 223 static const bool needsRelinking = false; 224 static const bool needsSize = false; 225 226private: 227 std::set<void *> freeSet; 228}; 229 230 231// 232// Stand-alone operations for a single structure web. 233// These simply create, use, and discard their operator objects internally. 234// 235template <class T> 236size_t size(T obj) 237{ 238 SizeWalker w; 239 walk(w, obj); 240 return w; 241} 242 243// Special version for const pointer's 244template <class T> 245size_t size(const T *obj) 246{ return size(const_cast<T *>(obj)); } 247 248 249template <class T> 250T *copy(const T *obj, void *addr) 251{ 252 if (obj == NULL) 253 return NULL; 254 CopyWalker w(addr); 255 walk(w, const_cast<T * &>(obj)); 256 return const_cast<T *>(obj); 257} 258 259template <class T> 260T *copy(const T *obj, Allocator &alloc, size_t size) 261{ 262 if (obj == NULL) 263 return NULL; 264 return copy(obj, alloc.malloc(size)); 265} 266 267template <class T> 268T *copy(const T *obj, Allocator &alloc = Allocator::standard()) 269{ 270 return obj ? copy(obj, alloc, size(obj)) : NULL; 271} 272 273 274template <class T> 275void relocate(T *obj, T *base) 276{ 277 if (obj) { 278 ReconstituteWalker w(LowLevelMemoryUtilities::difference(obj, base)); 279 walk(w, base); 280 } 281} 282 283 284// 285// chunkCopy and chunkFree can take pointer and non-pointer arguments. 286// Don't try to declare the T arguments const (overload resolution will 287// mess you over if you try). Just take const and nonconst Ts and take 288// the const away internally. 289// 290template <class T> 291typename Nonconst<T>::Type *chunkCopy(T *obj, Allocator &alloc = Allocator::standard()) 292{ 293 if (obj) { 294 ChunkCopyWalker w(alloc); 295 return walk(w, unconst_ref_cast<T *>(obj)); 296 } else 297 return NULL; 298} 299 300template <class T> 301T chunkCopy(T obj, Allocator &alloc = Allocator::standard()) 302{ 303 ChunkCopyWalker w(alloc); 304 walk(w, obj); 305 return obj; 306} 307 308template <class T> 309void chunkFree(T *obj, Allocator &alloc = Allocator::standard()) 310{ 311 if (obj) { 312 ChunkFreeWalker w(alloc); 313 walk(w, unconst_ref_cast<T *>(obj)); 314 } 315} 316 317template <class T> 318void chunkFree(const T &obj, Allocator &alloc = Allocator::standard()) 319{ 320 ChunkFreeWalker w(alloc); 321 walk(w, obj); 322} 323 324 325// 326// Copier combines SizeWalker and CopyWalker into one operational package. 327// this is useful if you need both the copy and its size (and don't want 328// to re-run size()). Copier (like copy()) only applies to one object. 329// 330template <class T> 331class Copier { 332public: 333 Copier(const T *obj, Allocator &alloc = Allocator::standard()) : allocator(alloc) 334 { 335 if (obj == NULL) { 336 mValue = NULL; 337 mLength = 0; 338 } else { 339 mLength = size(const_cast<T *>(obj)); 340#if BUG_GCC 341 mValue = reinterpret_cast<T *>(alloc.malloc(mLength)); 342#else 343 mValue = alloc.malloc<T>(mLength); 344#endif 345 mValue = copy(obj, mValue); 346 } 347 } 348 349 Copier(const T *obj, uint32 count, Allocator &alloc = Allocator::standard()) 350 : allocator(alloc) 351 { 352 if (obj == NULL) { 353 mValue = NULL; 354 mLength = 0; 355 } else { 356 SizeWalker sizer; 357 sizer.reserve(sizeof(T) * count); // initial vector size 358 for (uint32 n = 0; n < count; n++) 359 walk(sizer, const_cast<T &>(obj[n])); // dependent data sizes 360 mLength = sizer; 361#if BUG_GCC 362 mValue = reinterpret_cast<T *>(alloc.malloc(mLength)); 363#else 364 mValue = alloc.malloc<T>(mLength); 365#endif 366 CopyWalker copier(LowLevelMemoryUtilities::increment(mValue, sizeof(T) * count)); 367 for (uint32 n = 0; n < count; n++) { 368 mValue[n] = obj[n]; 369 walk(copier, mValue[n]); 370 } 371 } 372 } 373 374 Allocator &allocator; 375 376 ~Copier() { allocator.free(mValue); } 377 378 T *value() const { return mValue; } 379 operator T *() const { return value(); } 380 size_t length() const { return mLength; } 381 382 T *keep() { T *result = mValue; mValue = NULL; return result; } 383 384private: 385 T *mValue; 386 size_t mLength; 387}; 388 389 390} // end namespace DataWalkers 391} // end namespace Security 392 393#endif //_H_WALKERS 394