1/*
2 * Copyright (c) 2003, 2004, 2006-2008, 2011, 2012 Apple 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 * Modification History
26 *
27 * April 23, 2003		Allan Nathanson <ajn@apple.com>
28 * - initial revision
29 */
30
31
32#include "configd.h"
33#include "pattern.h"
34
35
36/*
37 * Notes:
38 *
39 * - pattern matching information is maintained in a dictionary (patternData).
40 * - the dictionary "key" is the regular expression being matched
41 * - the dictionary "value" is a CFArray with the following contents
42 *     [0]   = CFData consisting of the pre-compiled regular expression
43 *     [1]   = CFArray[CFNumber] consisting of the sessions watching this pattern
44 *     [2-n] = dynamic store keys which match this pattern
45 */
46
47
48typedef struct {
49	CFMutableArrayRef	pInfo;
50	CFDataRef		pRegex;
51} addContext, *addContextRef;
52
53
54static __inline__ void
55my_CFDictionaryApplyFunction(CFDictionaryRef			theDict,
56			     CFDictionaryApplierFunction	applier,
57			     void				*context)
58{
59	CFAllocatorRef	myAllocator;
60	CFDictionaryRef	myDict;
61
62	myAllocator = CFGetAllocator(theDict);
63	myDict      = CFDictionaryCreateCopy(myAllocator, theDict);
64	CFDictionaryApplyFunction(myDict, applier, context);
65	CFRelease(myDict);
66	return;
67}
68
69
70static Boolean
71keyMatchesPattern(CFStringRef key, CFDataRef pRegex)
72{
73	CFIndex			len;
74	Boolean			match		= FALSE;
75	regex_t			*preg;
76	int			reError;
77	char			str_q[256];
78	char *			str		= str_q;
79
80	/* convert store key to C string */
81	len = CFStringGetMaximumSizeForEncoding(CFStringGetLength(key), kCFStringEncodingASCII) + 1;
82	if (len > (CFIndex)sizeof(str_q))
83		str = CFAllocatorAllocate(NULL, len, 0);
84	if (_SC_cfstring_to_cstring(key, str, len, kCFStringEncodingASCII) == NULL) {
85		SCLog(TRUE, LOG_DEBUG, CFSTR("keyMatchesPattern(): could not convert store key to C string"));
86		goto done;
87	}
88
89	/* ALIGN: CF aligns to >8 byte boundries */
90	preg = (regex_t *)(void *)CFDataGetBytePtr(pRegex);
91
92	/* compare key to regular expression pattern */
93	reError = regexec(preg, str, 0, NULL, 0);
94	switch (reError) {
95		case 0 :
96			match = TRUE;
97			break;
98		case REG_NOMATCH :
99			/* no match */
100			break;
101		default : {
102			char	reErrBuf[256];
103
104			(void)regerror(reError, preg, reErrBuf, sizeof(reErrBuf));
105			SCLog(TRUE, LOG_DEBUG, CFSTR("keyMatchesPattern regexec(): %s"), reErrBuf);
106			break;
107		}
108	}
109
110    done :
111
112	if (str != str_q) CFAllocatorDeallocate(NULL, str);
113	return match;
114}
115
116
117static void
118identifyKeyForPattern(const void *key, void *val, void *context)
119{
120	CFStringRef		storeKey	= (CFStringRef)key;
121	CFDictionaryRef		storeValue	= (CFDictionaryRef)val;
122	CFMutableArrayRef	pInfo		= ((addContextRef)context)->pInfo;
123	CFDataRef		pRegex		= ((addContextRef)context)->pRegex;
124
125	if (!CFDictionaryContainsKey(storeValue, kSCDData)) {
126		/* if no data (yet) */
127		return;
128	}
129
130	if (keyMatchesPattern(storeKey, pRegex)) {
131		/* if we've got a match */
132		CFArrayAppendValue(pInfo, storeKey);
133	}
134
135	return;
136}
137
138
139static Boolean
140patternCompile(CFStringRef pattern, CFDataRef pRegex, CFStringRef *error)
141{
142	Boolean		append		= FALSE;
143	Boolean		insert		= FALSE;
144	CFIndex		len		= 0;
145	CFIndex		len_c;
146	Boolean		ok;
147	char		str_q[256];
148	char *		str		= str_q;
149
150	if (CFStringGetLength(pattern) == 0) {
151		SCLog(TRUE, LOG_ERR, CFSTR("patternCompile(): empty string"));
152	}
153
154	if (!CFStringHasPrefix(pattern, CFSTR("^"))) {
155		insert = TRUE;
156	}
157
158	if (!CFStringHasSuffix(pattern, CFSTR("$")) ||
159	     CFStringHasSuffix(pattern, CFSTR("\\$"))) {
160		append = TRUE;
161	}
162
163	/* if regex pattern is not bounded at both ends */
164	if (insert || append) {
165	      pattern = CFStringCreateWithFormat(NULL,
166						 NULL,
167						 CFSTR("%s%@%s"),
168						 insert ? "^" : "",
169						 pattern,
170						 append ? "$" : "");
171	}
172
173	len_c = CFStringGetBytes(pattern,
174				 CFRangeMake(0, CFStringGetLength(pattern)),
175				 kCFStringEncodingASCII,
176				 0,
177				 FALSE,
178				 NULL,
179				 0,
180				 &len);
181	if (len_c <= 0) {
182		SCLog(TRUE, LOG_ERR, CFSTR("patternCompile(): could not get buffer length for \"%@\""), pattern);
183		len = sizeof(str_q) - 1;
184	}
185	if (++len > (CFIndex)sizeof(str_q)) {
186		str = CFAllocatorAllocate(NULL, len, 0);
187	}
188	ok = (_SC_cfstring_to_cstring(pattern, str, len, kCFStringEncodingASCII) != NULL);
189	if (insert || append) {
190		CFRelease(pattern);
191	}
192	if (ok) {
193		regex_t	*preg;
194		int	reError;
195
196		/* ALIGN: CF aligns to >8 byte boundries */
197		preg = (regex_t *)(void *)CFDataGetBytePtr(pRegex);
198
199		reError = regcomp(preg, str, REG_EXTENDED);
200		if (reError != 0) {
201			char	reErrBuf[256];
202
203			(void)regerror(reError, preg, reErrBuf, sizeof(reErrBuf));
204			*error = CFStringCreateWithCString(NULL, reErrBuf, kCFStringEncodingASCII);
205#ifdef	DEBUG
206			SCLog(_configd_verbose, LOG_DEBUG, CFSTR("patternCompile regcomp(%s) failed: %s"), str, reErrBuf);
207#endif	/* DEBUG */
208			ok = FALSE;
209		}
210	} else {
211		*error = CFRetain(CFSTR("could not convert pattern to regex string"));
212#ifdef	DEBUG
213		SCLog(_configd_verbose, LOG_DEBUG, CFSTR("%@"), *error);
214#endif	/* DEBUG */
215	}
216
217	if (str != str_q)	CFAllocatorDeallocate(NULL, str);
218	return ok;
219}
220
221
222static void
223patternRelease(CFDataRef pRegex)
224{
225	regex_t		*preg;
226
227	/* ALIGN: CF aligns to >8 byte boundries */
228	preg = (regex_t *)(void *)CFDataGetBytePtr(pRegex);
229	regfree(preg);
230
231	return;
232}
233
234
235static CF_RETURNS_RETAINED CFMutableArrayRef
236patternCopy(CFStringRef	pattern)
237{
238	CFArrayRef	pInfo;
239
240	pInfo = CFDictionaryGetValue(patternData, pattern);
241	return (pInfo != NULL) ? CFArrayCreateMutableCopy(NULL, 0, pInfo) : NULL;
242}
243
244
245static CF_RETURNS_RETAINED CFMutableArrayRef
246patternNew(CFStringRef pattern)
247{
248	addContext		context;
249	CFStringRef		err	= NULL;
250	CFMutableArrayRef	pInfo;
251	CFMutableDataRef	pRegex;
252	CFArrayRef		pSessions;
253
254	/* create the pattern info */
255	pInfo = CFArrayCreateMutable(NULL, 0, &kCFTypeArrayCallBacks);
256
257	/* compile the regular expression from the pattern string. */
258	pRegex = CFDataCreateMutable(NULL, sizeof(regex_t));
259	CFDataSetLength(pRegex, sizeof(regex_t));
260	if (!patternCompile(pattern, pRegex, &err)) {
261		CFRelease(err);
262		CFRelease(pRegex);
263		CFRelease(pInfo);
264		return NULL;
265	}
266
267	/* add the compiled regular expression to the pattern info */
268	CFArrayAppendValue(pInfo, pRegex);
269
270	/* add the initial (empty) list of sessions watching this pattern */
271	pSessions = CFArrayCreate(NULL, NULL, 0, &kCFTypeArrayCallBacks);
272	CFArrayAppendValue(pInfo, pSessions);
273	CFRelease(pSessions);
274
275	/* identify/add all existing keys that match the specified pattern */
276	context.pInfo  = pInfo;
277	context.pRegex = pRegex;
278	my_CFDictionaryApplyFunction(storeData,
279				     (CFDictionaryApplierFunction)identifyKeyForPattern,
280				     &context);
281
282	CFRelease(pRegex);
283	return pInfo;
284}
285
286
287__private_extern__
288CFArrayRef
289patternCopyMatches(CFStringRef pattern)
290{
291	Boolean			isNew	= FALSE;
292	CFArrayRef		keys;
293	CFMutableArrayRef	pInfo;
294
295	/* find (or create new instance of) this pattern */
296	pInfo = patternCopy(pattern);
297	if (pInfo == NULL) {
298		/* if new pattern */
299		pInfo = patternNew(pattern);
300		if (pInfo == NULL) {
301			return NULL;
302		}
303
304		isNew = TRUE;
305	}
306
307	if (isNew) {
308		CFDataRef	pRegex;
309
310		pRegex = CFArrayGetValueAtIndex(pInfo, 0);
311		patternRelease(pRegex);
312	}
313
314	CFArrayReplaceValues(pInfo, CFRangeMake(0, 2), NULL, 0);
315	keys = CFArrayCreateCopy(NULL, pInfo);
316	CFRelease(pInfo);
317
318	return keys;
319}
320
321
322__private_extern__
323Boolean
324patternKeyMatches(CFStringRef pattern, CFStringRef key)
325{
326	Boolean			isNew	= FALSE;
327	Boolean			match	= FALSE;
328	CFMutableArrayRef	pInfo;
329	CFDataRef		pRegex;
330
331	/* find (or create new instance of) this pattern */
332	pInfo = patternCopy(pattern);
333	if (pInfo != NULL) {
334		CFIndex		n;
335
336		/* if existing pattern, check if known key */
337		n = CFArrayGetCount(pInfo);
338		match = (n > 2) &&
339			CFArrayContainsValue(pInfo, CFRangeMake(2, n - 2), key);
340		if (match) {
341			goto done;
342		}
343	} else {
344		/* if new pattern */
345		pInfo = patternNew(pattern);
346		if (pInfo == NULL) {
347			return FALSE;
348		}
349
350		isNew = TRUE;
351	}
352
353	pRegex = CFArrayGetValueAtIndex(pInfo, 0);
354	match = keyMatchesPattern(key, pRegex);
355
356	if (isNew) {
357		patternRelease(pRegex);
358	}
359
360    done :
361
362	CFRelease(pInfo);
363
364	return match;
365}
366
367
368__private_extern__
369Boolean
370patternAddSession(CFStringRef pattern, CFNumberRef sessionNum)
371{
372	CFIndex                 i;
373	CFIndex                 n;
374	CFMutableArrayRef       pInfo;
375	CFMutableArrayRef	pSessions;
376
377	/* find (or create new instance of) this pattern */
378	pInfo = patternCopy(pattern);
379	if (pInfo == NULL) {
380		/* if new pattern */
381		pInfo = patternNew(pattern);
382		if (pInfo == NULL) {
383			return FALSE;
384		}
385	}
386
387	/* add this session as a pattern watcher */
388	pSessions = (CFMutableArrayRef)CFArrayGetValueAtIndex(pInfo, 1);
389	pSessions = CFArrayCreateMutableCopy(NULL, 0, pSessions);
390	CFArrayAppendValue(pSessions, sessionNum);
391	CFArraySetValueAtIndex(pInfo, 1, pSessions);
392	CFRelease(pSessions);
393
394	/* update pattern watcher info */
395	CFDictionarySetValue(patternData, pattern, pInfo);
396
397	/* add this session as a watcher of any existing keys */
398	n = CFArrayGetCount(pInfo);
399	for (i = 2; i < n; i++) {
400		CFStringRef     matchingKey;
401
402		matchingKey = CFArrayGetValueAtIndex(pInfo, i);
403		_addWatcher(sessionNum, matchingKey);
404	}
405
406	CFRelease(pInfo);
407	return TRUE;
408}
409
410
411__private_extern__
412void
413patternRemoveSession(CFStringRef pattern, CFNumberRef sessionNum)
414{
415	CFIndex                 i;
416	CFIndex                 n;
417	CFMutableArrayRef       pInfo;
418	CFDataRef		pRegex;
419	CFMutableArrayRef	pSessions;
420
421	/* find instance of this pattern */
422	pInfo = patternCopy(pattern);
423	assert(pInfo != NULL);
424
425	/* remove this session as a watcher from all matching keys */
426	n = CFArrayGetCount(pInfo);
427	for (i = 2; i < n; i++) {
428		CFStringRef     matchingKey;
429
430		matchingKey = CFArrayGetValueAtIndex(pInfo, i);
431		_removeWatcher(sessionNum, matchingKey);
432	}
433
434	/* remove session from watchers */
435	pSessions = (CFMutableArrayRef)CFArrayGetValueAtIndex(pInfo, 1);
436	n = CFArrayGetCount(pSessions);
437	if (n > 1) {
438		/* if other sessions are watching this pattern */
439
440		pSessions = CFArrayCreateMutableCopy(NULL, 0, pSessions);
441		i = CFArrayGetFirstIndexOfValue(pSessions, CFRangeMake(0, n), sessionNum);
442		CFArrayRemoveValueAtIndex(pSessions, i);
443		CFArraySetValueAtIndex(pInfo, 1, pSessions);
444		CFRelease(pSessions);
445
446		CFDictionarySetValue(patternData, pattern, pInfo);
447	} else {
448		/* if no other sessions are watching this pattern */
449
450		pRegex = CFArrayGetValueAtIndex(pInfo, 0);
451		patternRelease(pRegex);
452		CFDictionaryRemoveValue(patternData, pattern);
453	}
454
455	CFRelease(pInfo);
456	return;
457}
458
459
460static void
461addKeyForPattern(const void *key, void *val, void *context)
462{
463	CFStringRef		pattern		= (CFStringRef)key;
464	CFArrayRef		pInfo		= (CFArrayRef)val;
465	CFStringRef		storeKey	= (CFStringRef)context;
466
467	CFIndex			len;
468	regex_t			*preg;
469	int			reError;
470	char			str_q[256];
471	char *			str		= str_q;
472
473	/* convert store key to C string */
474	len = CFStringGetMaximumSizeForEncoding(CFStringGetLength(storeKey), kCFStringEncodingASCII) + 1;
475	if (len > (CFIndex)sizeof(str_q))
476		str = CFAllocatorAllocate(NULL, len, 0);
477	if (_SC_cfstring_to_cstring(storeKey, str, len, kCFStringEncodingASCII) == NULL) {
478		SCLog(TRUE, LOG_DEBUG, CFSTR("addKeyForPattern(): could not convert store key to C string"));
479		goto done;
480	}
481
482	/* compare new store key to regular expression pattern */
483	/* ALIGN: CF aligns to >8 byte boundries */
484	preg = (regex_t *)(void *)CFDataGetBytePtr(CFArrayGetValueAtIndex(pInfo, 0));
485	reError = regexec(preg, str, 0, NULL, 0);
486	switch (reError) {
487		case 0 : {
488			/*
489			 * we've got a match
490			 */
491			CFIndex			i;
492			CFIndex			n;
493			CFMutableArrayRef	pInfo_new;
494			CFArrayRef		pSessions;
495
496			/* add watchers */
497			pSessions = CFArrayGetValueAtIndex(pInfo, 1);
498			n = CFArrayGetCount(pSessions);
499			for (i = 0; i < n; i++) {
500				CFNumberRef	sessionNum	= CFArrayGetValueAtIndex(pSessions, i);
501
502				_addWatcher(sessionNum, storeKey);
503			}
504
505			/* add key, update pattern watcher info */
506			pInfo_new = CFArrayCreateMutableCopy(NULL, 0, pInfo);
507			CFArrayAppendValue(pInfo_new, storeKey);
508			CFDictionarySetValue(patternData, pattern, pInfo_new);
509			CFRelease(pInfo_new);
510			break;
511		}
512		case REG_NOMATCH :
513			/* no match */
514			break;
515		default : {
516			char	reErrBuf[256];
517
518			(void)regerror(reError, preg, reErrBuf, sizeof(reErrBuf));
519			SCLog(TRUE, LOG_DEBUG, CFSTR("addKeyForPattern regexec(): %s"), reErrBuf);
520			break;
521		}
522	}
523
524    done :
525
526	if (str != str_q) CFAllocatorDeallocate(NULL, str);
527	return;
528}
529
530
531__private_extern__
532void
533patternAddKey(CFStringRef key)
534{
535	void	*context	= (void *)key;
536
537	my_CFDictionaryApplyFunction(patternData,
538				     (CFDictionaryApplierFunction)addKeyForPattern,
539				     context);
540
541	return;
542}
543
544
545static void
546removeKeyFromPattern(const void *key, void *val, void *context)
547{
548	CFStringRef		pattern		= (CFStringRef)key;
549	CFArrayRef		pInfo		= (CFArrayRef)val;
550	CFStringRef		storeKey	= (CFStringRef)context;
551
552	CFIndex			i;
553	CFIndex			n;
554	CFMutableArrayRef	pInfo_new;
555	CFArrayRef		pSessions;
556
557	n = CFArrayGetCount(pInfo);
558	if (n <= 2) {
559		/* if no keys match this pattern */
560		return;
561	}
562
563	i = CFArrayGetFirstIndexOfValue(pInfo, CFRangeMake(2, n-2), storeKey);
564	if (i == kCFNotFound) {
565		/* if this key wasn't matched by this pattern */
566		return;
567	}
568
569	/* remove key from pattern info */
570	pInfo_new = CFArrayCreateMutableCopy(NULL, 0, pInfo);
571	CFArrayRemoveValueAtIndex(pInfo_new, i);
572
573	/* remove watchers */
574	pSessions = CFArrayGetValueAtIndex(pInfo_new, 1);
575	n = CFArrayGetCount(pSessions);
576	for (i = 0; i < n; i++) {
577		CFNumberRef	sessionNum	= CFArrayGetValueAtIndex(pSessions, i);
578
579		_removeWatcher(sessionNum, storeKey);
580	}
581
582	CFDictionarySetValue(patternData, pattern, pInfo_new);
583	CFRelease(pInfo_new);
584	return;
585}
586
587
588__private_extern__
589void
590patternRemoveKey(CFStringRef key)
591{
592	void	*context	= (void *)key;
593
594	my_CFDictionaryApplyFunction(patternData,
595				     (CFDictionaryApplierFunction)removeKeyFromPattern,
596				     context);
597
598	return;
599}
600