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