]> git.saurik.com Git - apple/security.git/blob - OSX/libsecurity_transform/lib/GroupTransform.cpp
Security-58286.1.32.tar.gz
[apple/security.git] / OSX / libsecurity_transform / lib / GroupTransform.cpp
1 #include "GroupTransform.h"
2 #include "Utilities.h"
3 #include "misc.h"
4 #include <string>
5 #include <libkern/OSAtomic.h>
6
7 using namespace std;
8
9 CFStringRef kSecGroupTransformType = CFSTR("GroupTransform");
10
11 GroupTransform::GroupTransform() : Transform(kSecGroupTransformType, kSecGroupTransformType)
12 {
13 mMembers = CFArrayCreateMutable(NULL, 0, &kCFTypeArrayCallBacks);
14 mAllChildrenFinalized = dispatch_group_create();
15 mPendingStartupActivity = dispatch_group_create();
16 }
17
18 // Invoked by Transform::Finalize
19 void GroupTransform::FinalizePhase2()
20 {
21 // Any time afer mMembers is released this can be deleted, so we need a local.
22 CFArrayRef members = this->mMembers;
23 dispatch_group_notify(mPendingStartupActivity, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{
24 if (mMembers) {
25 this->mMembers = NULL;
26 CFReleaseSafe(members);
27 }
28 });
29
30 // Delay the final delete of the group until all children are gone (and thus unable to die while referencing us).
31 dispatch_group_notify(mAllChildrenFinalized, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{
32 delete this;
33 });
34 }
35
36 void GroupTransform::StartingExecutionInGroup()
37 {
38 this->mIsActive = true;
39 dispatch_group_enter(mPendingStartupActivity);
40 dispatch_group_enter(mAllChildrenFinalized);
41 }
42
43 void GroupTransform::StartedExecutionInGroup(bool succesful)
44 {
45 dispatch_group_leave(mPendingStartupActivity);
46 dispatch_group_leave(mAllChildrenFinalized);
47 }
48
49 bool GroupTransform::validConnectionPoint(CFStringRef attributeName)
50 {
51 // We don't want connections to/from unexported attributes
52 return NULL != this->getAH(attributeName, false);
53 }
54
55 GroupTransform::~GroupTransform()
56 {
57 // mMembers already released (via FinalizePhase2)
58 dispatch_release(mAllChildrenFinalized);
59 dispatch_release(mPendingStartupActivity);
60 }
61
62 void GroupTransform::ChildStartedFinalization(Transform *child)
63 {
64 // child started finalizing before the group?? Likely client over release.
65 (void)transforms_assume(this->mIsFinalizing);
66 dispatch_group_leave(mAllChildrenFinalized);
67 }
68
69 CFTypeRef GroupTransform::Make()
70 {
71 return CoreFoundationHolder::MakeHolder(kSecGroupTransformType, new GroupTransform());
72 }
73
74 static CFComparisonResult tr_cmp(const void *val1, const void *val2, void *context)
75 {
76 return (((intptr_t) val1 == (intptr_t) val2) ? kCFCompareEqualTo
77 : ((intptr_t) val1 > (intptr_t) val2) ? kCFCompareGreaterThan
78 : kCFCompareLessThan);
79 }
80
81 bool GroupTransform::HasMember(SecTransformRef member)
82 {
83 // find the transform in the group
84 CFIndex numMembers = CFArrayGetCount(mMembers);
85 CFIndex i;
86
87 for (i = 0; i < numMembers; ++i)
88 {
89 if (CFArrayGetValueAtIndex(mMembers, i) == member)
90 {
91 return true;
92 }
93 }
94
95 return false;
96 }
97
98
99
100 void GroupTransform::RemoveMemberFromGroup(SecTransformRef member)
101 {
102 // find the transform in the group and remove it
103 // XXX: this would be a lot faster if it used CFArrayBSearchValues
104 CFIndex numMembers = CFArrayGetCount(mMembers);
105 CFIndex i;
106
107 for (i = 0; i < numMembers; ++i)
108 {
109 if (CFArrayGetValueAtIndex(mMembers, i) == member)
110 {
111 // removing the item will release it, so we don't need an explicit release
112 CFArrayRemoveValueAtIndex(mMembers, i);
113 numMembers = CFArrayGetCount(mMembers);
114 dispatch_group_leave(mAllChildrenFinalized);
115 }
116 }
117 }
118
119 void GroupTransform::AddAllChildrenFinalizedCallback(dispatch_queue_t run_on, dispatch_block_t callback)
120 {
121 dispatch_group_notify(mAllChildrenFinalized, run_on, callback);
122 }
123
124
125 void GroupTransform::AddMemberToGroup(SecTransformRef member)
126 {
127 // set a backlink to this group in the child (used for abort and other purposes)
128 Transform* transform = (Transform*) CoreFoundationHolder::ObjectFromCFType(member);
129 // XXX: it seems like we should be able to ensure that we are the only caller to SetGroup, and that if the group is set to us we could skip this search...
130 transform->SetGroup(this);
131 if (transform == this) {
132 // We don't want to be in our own membership list, at a minimum
133 // that makes reference counts cranky.
134 return;
135 }
136
137 // check to make sure that member is not already in the group (the bsearch code is a bit more complex, but cuts run time for the 8163542 test from about 40 minutes to under a minute)
138 CFIndex numMembers = CFArrayGetCount(mMembers);
139 CFRange range = {0, numMembers};
140 CFIndex at = CFArrayBSearchValues(mMembers, range, member, tr_cmp, NULL);
141 SecTransformRef candiate = (at < numMembers) ? CFArrayGetValueAtIndex(mMembers, at) : NULL;
142 if (member == candiate) {
143 return;
144 }
145
146 CFArrayInsertValueAtIndex(mMembers, at, member);
147 dispatch_group_enter(mAllChildrenFinalized);
148 }
149
150
151
152 std::string GroupTransform::DebugDescription()
153 {
154 return Transform::DebugDescription() + ": GroupTransform";
155 }
156
157
158
159 class GroupTransformFactory : public TransformFactory
160 {
161 public:
162 GroupTransformFactory();
163
164 virtual CFTypeRef Make();
165 };
166
167
168
169 TransformFactory* GroupTransform::MakeTransformFactory()
170 {
171 return new GroupTransformFactory();
172 }
173
174
175
176 GroupTransformFactory::GroupTransformFactory() : TransformFactory(kSecGroupTransformType)
177 {
178 }
179
180
181
182 CFTypeRef GroupTransformFactory::Make()
183 {
184 return GroupTransform::Make();
185 }
186
187
188
189 CFTypeID GroupTransform::GetCFTypeID()
190 {
191 return CoreFoundationObject::FindObjectType(kSecGroupTransformType);
192 }
193
194
195
196
197 SecTransformRef GroupTransform::FindFirstTransform()
198 {
199 // look for a transform that has no connections to INPUT (prefer ones where INPUT is required)
200 CFRange range;
201 range.location = 0;
202 range.length = CFArrayGetCount(mMembers);
203 SecTransformRef items[range.length];
204 SecTransformRef maybe = NULL;
205
206 CFArrayGetValues(mMembers, range, items);
207
208 CFIndex i;
209 for (i = 0; i < range.length; ++i)
210 {
211 SecTransformRef tr = (SecTransformRef) items[i];
212 Transform* t = (Transform*) CoreFoundationHolder::ObjectFromCFType(tr);
213 SecTransformAttributeRef in = getAH(kSecTransformInputAttributeName, false);
214 if (!t->GetMetaAttribute(in, kSecTransformMetaAttributeHasInboundConnection)) {
215 maybe = tr;
216 if (t->GetMetaAttribute(in, kSecTransformMetaAttributeRequired)) {
217 return tr;
218 }
219 }
220 }
221
222 return maybe;
223 }
224
225
226 SecTransformRef GroupTransform::GetAnyMember()
227 {
228 if (CFArrayGetCount(mMembers)) {
229 return CFArrayGetValueAtIndex(mMembers, 0);
230 } else {
231 return NULL;
232 }
233 }
234
235 // Pretty horrible kludge -- we will do Very Bad Things if someone names their transform <anything>Monitor
236 SecTransformRef GroupTransform::FindMonitor()
237 {
238 // list all transforms in the group
239 CFRange range;
240 range.location = 0;
241 range.length = CFArrayGetCount(mMembers);
242 SecTransformRef items[range.length];
243 CFArrayGetValues(mMembers, range, items);
244
245 // check each item to see if it is a monitor
246 CFIndex i;
247 for (i = 0; i < range.length; ++i)
248 {
249 SecTransformRef tr = (SecTransformRef) items[i];
250 Transform* t = (Transform*) CoreFoundationHolder::ObjectFromCFType(tr);
251
252 if (CFStringHasSuffix(t->mTypeName, CFSTR("Monitor"))) {
253 return tr;
254 }
255 }
256
257 return NULL;
258 }
259
260
261
262 SecTransformRef GroupTransform::FindLastTransform()
263 {
264 // If there's a monitor attached to this transform, the last transform is
265 // the transform that points to it. Otherwise, the last transform is the
266 // one that has nothing connected to its output attribute and said attribute
267 // is marked as requiring an outbound connection.
268
269 // WARNING: if this function and Transform::ExecuteOperation disagree about
270 // where to attach a monitor things could get funky. It would be very nice
271 // to implement one of these in terms of the other.
272
273 SecTransformRef lastOrMonitor = FindMonitor(); // this will either be NULL or the monitor.
274 // We win either way.
275
276 // list all transforms in the group
277 CFRange range;
278 range.location = 0;
279 range.length = CFArrayGetCount(mMembers);
280 SecTransformRef items[range.length];
281 CFArrayGetValues(mMembers, range, items);
282
283 // if the output attribute of a transform matches our target, we win
284 CFIndex i;
285 for (i = 0; i < range.length; ++i)
286 {
287 Transform* tr = (Transform*) CoreFoundationHolder::ObjectFromCFType(items[i]);
288
289 // get the output attribute for the transform
290 transform_attribute* ta = tr->getTA(kSecTransformOutputAttributeName, false);
291
292 if (lastOrMonitor == NULL)
293 {
294 if (ta->requires_outbound_connection && (ta->connections == NULL || (CFArrayGetCount(ta->connections) == 0)))
295 {
296 // this a transform with an unattached OUTPUT with RequiresOutboundConnection true
297 return items[i];
298 }
299 } else {
300 if (ta->connections) {
301 // get all of the connections for that attribute, and see if one of them is the monitor
302 CFRange connectionRange;
303 connectionRange.location = 0;
304 connectionRange.length = CFArrayGetCount(ta->connections);
305 SecTransformAttributeRef attributeHandles[connectionRange.length];
306 CFArrayGetValues(ta->connections, connectionRange, attributeHandles);
307
308 CFIndex j;
309 for (j = 0; j < connectionRange.length; ++j)
310 {
311 transform_attribute* ta = ah2ta(attributeHandles[j]);
312 if (ta->transform->GetCFObject() == lastOrMonitor)
313 {
314 return items[i];
315 }
316 }
317 }
318 }
319 }
320
321 // this chain is seriously whacked!!!
322 return NULL;
323 }
324
325 SecTransformRef GroupTransform::FindByName(CFStringRef name)
326 {
327 __block SecTransformRef ret = NULL;
328 static CFErrorRef early_return = CFErrorCreate(NULL, kCFErrorDomainPOSIX, EEXIST, NULL);
329
330 ForAllNodes(true, true, ^(Transform *t){
331 if (!CFStringCompare(name, t->GetName(), 0)) {
332 ret = t->GetCFObject();
333 return early_return;
334 }
335 return (CFErrorRef)NULL;
336 });
337
338 return ret;
339 }
340
341 CFDictionaryRef GroupTransform::Externalize(CFErrorRef* error)
342 {
343 return NULL;
344 }
345
346 // Visit all children once. Unlike ForAllNodes there is no way to early exit, nor a way to return a status.
347 // Returns when all work is scheduled, use group to determine completion of work.
348 // See also ForAllNodes below.
349 void GroupTransform::ForAllNodesAsync(bool opExecutesOnGroups, dispatch_group_t group, Transform::TransformAsyncOperation op)
350 {
351 dispatch_group_enter(group);
352 CFIndex lim = mMembers ? CFArrayGetCount(mMembers) : 0;
353
354 if (opExecutesOnGroups)
355 {
356 dispatch_group_async(group, mDispatchQueue, ^{
357 op(this);
358 });
359 }
360
361 for(CFIndex i = 0; i < lim; ++i)
362 {
363 SecTransformRef tr = CFArrayGetValueAtIndex(mMembers, i);
364 Transform *t = (Transform*)CoreFoundationHolder::ObjectFromCFType(tr);
365
366 if (CFGetTypeID(tr) == SecGroupTransformGetTypeID()) {
367 GroupTransform *g = (GroupTransform*)t;
368 g->ForAllNodesAsync(true, group, op);
369 } else {
370 dispatch_group_async(group, t->mDispatchQueue, ^{
371 op(t);
372 });
373 }
374 }
375 dispatch_group_leave(group);
376 }
377
378 // Visit all nodes once (at most), attempts to stop if any op
379 // returns non-NULL (if parallel is true in flight ops are not
380 // stopped). Returns when all work is complete, and returns
381 // the "first" non-NULL op value (or NULL if all ops returned
382 // NULL). Uses ForAllNodes below to do the dirty work.
383 CFErrorRef GroupTransform::ForAllNodes(bool parallel, bool opExecutesOnGroups, Transform::TransformOperation op)
384 {
385 dispatch_group_t inner_group = dispatch_group_create();
386
387 CFErrorRef err = NULL;
388 RecurseForAllNodes(inner_group, &err, parallel, opExecutesOnGroups, op);
389
390 dispatch_group_wait(inner_group, DISPATCH_TIME_FOREVER);
391 dispatch_release(inner_group);
392
393 return err;
394 }
395
396 // Visit all children once (at most), because groups can appear in
397 // multiple other groups use visitedGroups (protected by
398 // rw_queue) to avoid multiple visits. Will stop if an op
399 // returns non-NULL.
400 // (Used only by ForAllNodes above)
401 void GroupTransform::RecurseForAllNodes(dispatch_group_t group, CFErrorRef *err_, bool parallel, bool opExecutesOnGroups, Transform::TransformOperation op)
402 {
403 __block CFErrorRef *err = err_;
404 void (^set_error)(CFErrorRef new_err) = ^(CFErrorRef new_err) {
405 if (new_err) {
406 if (!OSAtomicCompareAndSwapPtrBarrier(NULL, (void *)new_err, (void**)err)) {
407 CFReleaseNull(new_err);
408 }
409 }
410 };
411 void (^runOp)(Transform *t) = ^(Transform *t){
412 if (parallel) {
413 dispatch_group_async(group, t->mDispatchQueue, ^{
414 set_error(op(t));
415 });
416 } else {
417 set_error(op(t));
418 }
419 };
420
421 dispatch_group_enter(group);
422 if (opExecutesOnGroups) {
423 runOp(this);
424 }
425
426
427 CFIndex i, lim = CFArrayGetCount(mMembers);
428
429 for(i = 0; i < lim && !*err; ++i) {
430 SecTransformRef tr = CFArrayGetValueAtIndex(mMembers, i);
431 Transform *t = (Transform*)CoreFoundationHolder::ObjectFromCFType(tr);
432
433 if (CFGetTypeID(tr) == SecGroupTransformGetTypeID()) {
434 GroupTransform *g = (GroupTransform*)t;
435 g->RecurseForAllNodes(group, err, parallel, opExecutesOnGroups, op);
436 } else {
437 runOp(t);
438 }
439 }
440
441 dispatch_group_leave(group);
442 }
443
444 // Return a dot (GraphViz) description of the group.
445 // For debugging use. Exact content and style may
446 // change. Currently all transforms and attributes
447 // are displayed, but only string values are shown
448 // (and no meta attributes are indicated).
449 CFStringRef GroupTransform::DotForDebugging()
450 {
451 __block CFMutableStringRef result = CFStringCreateMutable(NULL, 0);
452 CFStringAppend(result, CFSTR("digraph \"G\" {\n"));
453
454 dispatch_queue_t collect_nodes = dispatch_queue_create("dot-node-collector", NULL);
455 dispatch_group_t complete_nodes = dispatch_group_create();
456 dispatch_queue_t collect_connections = dispatch_queue_create("dot-connection-collector", NULL);
457 dispatch_group_t complete_connections = dispatch_group_create();
458 // Before we reference a node we need it to be declared in the correct
459 // graph cluster, so we defer all the connection output until we
460 // have all the nodes defined.
461 dispatch_suspend(collect_connections);
462
463
464 this->ForAllNodesAsync(true, complete_nodes, ^(Transform *t) {
465 CFStringRef name = t->GetName();
466 __block CFMutableStringRef group_nodes_out = CFStringCreateMutable(NULL, 0);
467 __block CFMutableStringRef group_connections_out = CFStringCreateMutable(NULL, 0);
468 CFStringRef line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\tsubgraph \"cluster_%@\" {\n"), name);
469 CFStringAppend(group_nodes_out, line_out);
470 CFReleaseNull(line_out);
471 line_out = NULL;
472
473 CFIndex n_attributes = t->GetAttributeCount();
474 transform_attribute **attributes = (transform_attribute **)alloca(n_attributes * sizeof(transform_attribute *));
475 t->TAGetAll(attributes);
476 CFMutableArrayRef most_dot_names = CFArrayCreateMutable(NULL, n_attributes -1, &kCFTypeArrayCallBacks);
477 for(int i = 0; i < n_attributes; i++) {
478 CFStringRef label = attributes[i]->name;
479 if (attributes[i]->value) {
480 if (CFGetTypeID(attributes[i]->value) == CFStringGetTypeID()) {
481 label = CFStringCreateWithFormat(NULL, NULL, CFSTR("%@=%@"), attributes[i]->name, attributes[i]->value);
482 }
483 }
484 if (!label) {
485 label = CFStringCreateCopy(NULL, attributes[i]->name);
486 }
487
488 CFStringRef dot_node_name = CFStringCreateWithFormat(NULL, NULL, CFSTR("\"%@#%@\""), name, attributes[i]->name);
489 if (CFStringCompare(CFSTR("NAME"), label, 0)) {
490 CFArrayAppendValue(most_dot_names, dot_node_name);
491 }
492 line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t\t%@ [shape=plaintext, label=\"%@\"]\n"), dot_node_name, label);
493 CFStringAppend(group_nodes_out, line_out);
494 CFReleaseNull(line_out);
495 line_out = NULL;
496 CFReleaseNull(label);
497
498 CFIndex n_connections = attributes[i]->connections ? CFArrayGetCount(attributes[i]->connections) : 0;
499 for(int j = 0; j < n_connections; j++) {
500 transform_attribute *connected_to = ah2ta(CFArrayGetValueAtIndex(attributes[i]->connections, j));
501 line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t%@ -> \"%@#%@\"\n"), dot_node_name, connected_to->transform->GetName(), connected_to->name);
502 CFStringAppend(group_connections_out, line_out);
503 CFReleaseNull(line_out);
504 }
505
506 CFSafeRelease(dot_node_name);
507 }
508
509 CFStringRef combinedString = CFStringCreateByCombiningStrings(NULL, most_dot_names, CFSTR(" "));
510 line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t\t\"%@#NAME\" -> { %@ } [style=invis]\n\t}\n"), name, combinedString);
511 CFStringAppend(group_nodes_out, line_out);
512 CFReleaseNull(line_out);
513 CFSafeRelease(most_dot_names);
514 CFSafeRelease(combinedString);
515 if (t->mGroup) {
516 line_out = CFStringCreateWithFormat(NULL, NULL, CFSTR("\t\"%@#NAME\" -> \"%@#NAME\" [style=dotted,weight=5]\n"), name, t->mGroup->GetName());
517 CFStringAppend(group_connections_out, line_out);
518 CFReleaseNull(line_out);
519 }
520 line_out = NULL;
521
522 dispatch_async(collect_nodes, ^(void) {
523 CFStringAppend(result, group_nodes_out);
524 CFReleaseNull(group_nodes_out);
525 });
526 dispatch_group_async(complete_connections, collect_connections, ^(void) {
527 // We don't really need to append to result on the collect_nodes queue
528 // because we happen to know no more work is going on on the collect_nodes
529 // queue, but if that ever changed we would have a hard to track down bug...
530 dispatch_async(collect_nodes, ^(void) {
531 CFStringAppend(result, group_connections_out);
532 CFReleaseNull(group_connections_out);
533 });
534 });
535 });
536
537 dispatch_group_wait(complete_nodes, DISPATCH_TIME_FOREVER);
538 dispatch_release(complete_nodes);
539 dispatch_resume(collect_connections);
540 dispatch_release(collect_connections);
541 dispatch_group_wait(complete_connections, DISPATCH_TIME_FOREVER);
542 dispatch_release(complete_connections);
543
544 dispatch_sync(collect_nodes, ^{
545 CFStringAppend(result, CFSTR("}\n"));
546 });
547 dispatch_release(collect_nodes);
548 return result;
549 }