1/*
2 * Copyright (c) 2007-2010 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#include <unistd.h>
25#include <stdlib.h>
26#include <stdio.h>
27#include <sys/errno.h>
28#include <string.h>
29#include <sys/types.h>
30#include <time.h>
31#include <asl_core.h>
32#include <asl_msg.h>
33#include <asl_msg_list.h>
34#include <asl_private.h>
35#include "asl_memory.h"
36
37#define DEFAULT_MAX_RECORDS 2000
38#define DEFAULT_MAX_STRING_MEMORY 4096000
39#define MEM_STRING_HEADER_SIZE 8
40
41#define forever for(;;)
42
43uint32_t
44asl_memory_statistics(asl_memory_t *s, asl_msg_t **msg)
45{
46	asl_msg_t * out;
47	uint32_t i, n;
48	uint64_t size;
49	char str[256];
50
51	if (s == NULL) return ASL_STATUS_INVALID_STORE;
52	if (msg == NULL) return ASL_STATUS_INVALID_ARG;
53
54	out = asl_msg_new(ASL_TYPE_MSG);
55	if (out == NULL) return ASL_STATUS_NO_MEMORY;
56
57	size = sizeof(asl_memory_t);
58	size += ((s->record_count + 1) * sizeof(mem_record_t));
59
60	for (i = 0; i < s->string_count; i++)
61	{
62		size += MEM_STRING_HEADER_SIZE;
63		if (((mem_string_t *)s->string_cache[i])->str != NULL) size += (strlen(((mem_string_t *)s->string_cache[i])->str) + 1);
64	}
65
66	snprintf(str, sizeof(str), "%llu", size);
67	asl_msg_set_key_val(out, "Size", str);
68
69	n = 0;
70	for (i = 0; i < s->record_count; i++) if (s->record[i]->mid != 0) n++;
71
72	snprintf(str, sizeof(str), "%u", s->record_count);
73	asl_msg_set_key_val(out, "MaxRecords", str);
74
75	snprintf(str, sizeof(str), "%u", n);
76	asl_msg_set_key_val(out, "RecordCount", str);
77
78	snprintf(str, sizeof(str), "%u", s->string_count);
79	asl_msg_set_key_val(out, "StringCount", str);
80
81	snprintf(str, sizeof(str), "%u", s->curr_string_mem);
82	asl_msg_set_key_val(out, "StringMemory", str);
83
84	snprintf(str, sizeof(str), "%u", s->max_string_mem);
85	asl_msg_set_key_val(out, "MaxStringMemory", str);
86
87	*msg = out;
88	return ASL_STATUS_OK;
89}
90
91uint32_t
92asl_memory_close(asl_memory_t *s)
93{
94	uint32_t i;
95
96	if (s == NULL) return ASL_STATUS_OK;
97
98	if (s->record != NULL)
99	{
100		for (i = 0; i < s->record_count; i++)
101		{
102			if (s->record[i] != NULL) free(s->record[i]);
103			s->record[i] = NULL;
104		}
105
106		free(s->record);
107		s->record = NULL;
108	}
109
110	if (s->buffer_record != NULL) free(s->buffer_record);
111
112	if (s->string_cache != NULL)
113	{
114		for (i = 0; i < s->string_count; i++)
115		{
116			if (s->string_cache[i] != NULL) free(s->string_cache[i]);
117			s->string_cache[i] = NULL;
118		}
119
120		free(s->string_cache);
121		s->string_cache = NULL;
122	}
123
124	free(s);
125
126	return ASL_STATUS_OK;
127}
128
129uint32_t
130asl_memory_open(uint32_t max_records, size_t max_str_mem, asl_memory_t **s)
131{
132	asl_memory_t *out;
133	uint32_t i;
134
135	if (s == NULL) return ASL_STATUS_INVALID_ARG;
136
137	if (max_records == 0) max_records = DEFAULT_MAX_RECORDS;
138	if (max_str_mem == 0) max_str_mem = DEFAULT_MAX_STRING_MEMORY;
139
140	out = calloc(1, sizeof(asl_memory_t));
141	if (out == NULL) return ASL_STATUS_NO_MEMORY;
142
143	out->max_string_mem = max_str_mem;
144
145	out->record_count = max_records;
146	out->record = (mem_record_t **)calloc(max_records, sizeof(mem_record_t *));
147	if (out->record == NULL)
148	{
149		free(out);
150		return ASL_STATUS_NO_MEMORY;
151	}
152
153	for (i = 0; i < max_records; i++)
154	{
155		out->record[i] = (mem_record_t *)calloc(1, sizeof(mem_record_t));
156		if (out->record[i] == NULL)
157		{
158			asl_memory_close(out);
159			return ASL_STATUS_NO_MEMORY;
160		}
161	}
162
163	out->buffer_record = (mem_record_t *)calloc(1, sizeof(mem_record_t));
164	if (out->buffer_record == NULL)
165	{
166		asl_memory_close(out);
167		return ASL_STATUS_NO_MEMORY;
168	}
169
170	*s = out;
171	return ASL_STATUS_OK;
172}
173
174static mem_string_t *
175mem_string_new(const char *str, uint32_t len, uint32_t hash)
176{
177	mem_string_t *out;
178	size_t ss;
179
180	if (str == NULL) return NULL;
181
182	ss = MEM_STRING_HEADER_SIZE + len + 1;
183	out = (mem_string_t *)calloc(1, ss);
184	if (out == NULL) return NULL;
185
186	out->hash = hash;
187	out->refcount = 1;
188	memcpy(out->str, str, len);
189
190	return out;
191}
192
193/*
194 * Find the first hash greater than or equal to a given hash in the string cache.
195 * Return s->string_count if hash is greater that or equal to last hash in the string cache.
196 * Caller must check if the hashes match or not.
197 *
198 * This routine is used both to find strings in the cache and to determine where to insert
199 * new strings.  Note that the caller needs to do extra work after calling this routine.
200 */
201static uint32_t
202asl_memory_string_cache_search_hash(asl_memory_t *s, uint32_t hash)
203{
204	uint32_t top, bot, mid, range;
205	mem_string_t *ms;
206
207	if (s->string_count == 0) return 0;
208	if (s->string_count == 1)
209	{
210		ms = (mem_string_t *)s->string_cache[0];
211		if (hash < ms->hash) return 0;
212		return 1;
213	}
214
215	range = top = s->string_count - 1;
216	bot = 0;
217	mid = top / 2;
218
219	while (range > 1)
220	{
221		ms = (mem_string_t *)s->string_cache[mid];
222
223		if (hash == ms->hash)
224		{
225			while (mid > 0)
226			{
227				ms = (mem_string_t *)s->string_cache[mid - 1];
228				if (hash != ms->hash) break;
229				mid--;
230			}
231
232			return mid;
233		}
234		else
235		{
236			ms = (mem_string_t *)s->string_cache[mid];
237			if (hash < ms->hash) top = mid;
238			else bot = mid;
239		}
240
241		range = top - bot;
242		mid = bot + (range / 2);
243	}
244
245	ms = (mem_string_t *)s->string_cache[bot];
246	if (hash <= ms->hash) return bot;
247
248	ms = (mem_string_t *)s->string_cache[top];
249	if (hash <= ms->hash) return top;
250
251	return s->string_count;
252}
253
254/*
255 * Search the string cache.
256 * If the string is in the cache, increment refcount and return it.
257 * If the string is not in cache and create flag is on, create a new string.
258 * Otherwise, return NULL.
259 */
260static mem_string_t *
261asl_memory_string_retain(asl_memory_t *s, const char *str, int create)
262{
263	uint32_t i, where, hash, len;
264	mem_string_t *new;
265
266	if (s == NULL) return NULL;
267	if (str == NULL) return NULL;
268	len = strlen(str);
269
270	/* check the cache */
271	hash = asl_core_string_hash(str, len);
272	where = asl_memory_string_cache_search_hash(s, hash);
273
274	/* asl_memory_string_cache_search_hash just tells us where to look */
275	if (where < s->string_count)
276	{
277		while (((mem_string_t *)(s->string_cache[where]))->hash == hash)
278		{
279			if (!strcmp(str, ((mem_string_t *)(s->string_cache[where]))->str))
280			{
281				((mem_string_t *)(s->string_cache[where]))->refcount++;
282				return s->string_cache[where];
283			}
284
285			where++;
286		}
287	}
288
289	/* not found */
290	if (create == 0) return NULL;
291
292	/* create a new mem_string_t and insert into the cache at index 'where' */
293	if (s->string_count == 0)
294	{
295		s->string_cache = (void **)calloc(1, sizeof(void *));
296	}
297	else
298	{
299		s->string_cache = (void **)reallocf(s->string_cache, (s->string_count + 1) * sizeof(void *));
300		for (i = s->string_count; i > where; i--) s->string_cache[i] = s->string_cache[i - 1];
301	}
302
303	if (s->string_cache == NULL)
304	{
305		s->string_count = 0;
306		return NULL;
307	}
308
309	new = mem_string_new(str, len, hash);
310	if (new == NULL) return NULL;
311
312	s->curr_string_mem += (MEM_STRING_HEADER_SIZE + len + 1);
313	s->string_cache[where] = new;
314	s->string_count++;
315
316	return s->string_cache[where];
317}
318
319static uint32_t
320asl_memory_string_release(asl_memory_t *s, mem_string_t *m)
321{
322	uint32_t i, where;
323
324	if (s == NULL) return ASL_STATUS_INVALID_STORE;
325	if (m == NULL) return ASL_STATUS_OK;
326
327	if (m->refcount > 0) m->refcount--;
328	if (m->refcount > 0) return ASL_STATUS_OK;
329
330	where = asl_memory_string_cache_search_hash(s, m->hash);
331	if (((mem_string_t *)(s->string_cache[where]))->hash != m->hash) return ASL_STATUS_OK;
332
333	while (s->string_cache[where] != m)
334	{
335		if (((mem_string_t *)(s->string_cache[where]))->hash != m->hash) return ASL_STATUS_OK;
336
337		where++;
338		if (where >= s->string_count) return ASL_STATUS_OK;
339	}
340
341	for (i = where + 1; i < s->string_count; i++) s->string_cache[i - 1] = s->string_cache[i];
342
343	s->curr_string_mem -= (MEM_STRING_HEADER_SIZE + strlen(m->str) + 1);
344
345	free(m);
346	s->string_count--;
347
348	if (s->string_count == 0)
349	{
350		free(s->string_cache);
351		s->string_cache = NULL;
352		return ASL_STATUS_OK;
353	}
354
355	s->string_cache = (void **)reallocf(s->string_cache, s->string_count * sizeof(void *));
356	if (s->string_cache == NULL)
357	{
358		s->string_count = 0;
359		return ASL_STATUS_NO_MEMORY;
360	}
361
362	return ASL_STATUS_OK;
363}
364
365/*
366 * Release all a record's strings and reset it's values
367 */
368static void
369asl_memory_record_clear(asl_memory_t *s, mem_record_t *r)
370{
371	uint32_t i;
372
373	if (s == NULL) return;
374	if (r == NULL) return;
375
376	asl_memory_string_release(s, r->host);
377	asl_memory_string_release(s, r->sender);
378	asl_memory_string_release(s, r->sender_mach_uuid);
379	asl_memory_string_release(s, r->facility);
380	asl_memory_string_release(s, r->message);
381	asl_memory_string_release(s, r->refproc);
382	asl_memory_string_release(s, r->session);
383
384	for (i = 0; i < r->kvcount; i++) asl_memory_string_release(s, r->kvlist[i]);
385
386	if (r->kvlist != NULL) free(r->kvlist);
387	memset(r, 0, sizeof(mem_record_t));
388}
389
390static void
391asl_memory_record_free(asl_memory_t *s, mem_record_t *r)
392{
393	asl_memory_record_clear(s, r);
394	free(r);
395}
396
397/*
398 * Encode an asl_msg_t as a record structure.
399 * Creates and caches strings.
400 */
401static uint32_t
402asl_memory_message_encode(asl_memory_t *s, asl_msg_t *msg)
403{
404	uint32_t x;
405	mem_string_t *k, *v;
406	mem_record_t *r;
407	const char *key, *val;
408
409	if (s == NULL) return ASL_STATUS_INVALID_STORE;
410	if (s->buffer_record == NULL) return ASL_STATUS_INVALID_STORE;
411	if (msg == NULL) return ASL_STATUS_INVALID_MESSAGE;
412
413	r = s->buffer_record;
414
415	memset(r, 0, sizeof(mem_record_t));
416
417	r->flags = 0;
418	r->level = ASL_LEVEL_DEBUG;
419	r->pid = -1;
420	r->uid = -2;
421	r->gid = -2;
422	r->ruid = -1;
423	r->rgid = -1;
424	r->time = (uint64_t)-1;
425	r->nano = (uint32_t)-1;
426
427	key = NULL;
428	val = NULL;
429
430	for (x = asl_msg_fetch((asl_msg_t *)msg, 0, &key, &val, NULL); x != IndexNull; x = asl_msg_fetch((asl_msg_t *)msg, x, &key, &val, NULL))
431	{
432		if (key == NULL) continue;
433
434		else if (!strcmp(key, ASL_KEY_TIME))
435		{
436			if (val != NULL) r->time = asl_core_parse_time(val, NULL);
437		}
438		else if (!strcmp(key, ASL_KEY_TIME_NSEC))
439		{
440			if (val != NULL) r->nano = atoi(val);
441		}
442		else if (!strcmp(key, ASL_KEY_HOST))
443		{
444			if (val != NULL) r->host = asl_memory_string_retain(s, val, 1);
445		}
446		else if (!strcmp(key, ASL_KEY_SENDER))
447		{
448			if (val != NULL) r->sender = asl_memory_string_retain(s, val, 1);
449		}
450		else if (!strcmp(key, ASL_KEY_PID))
451		{
452			if (val != NULL) r->pid = atoi(val);
453		}
454		else if (!strcmp(key, ASL_KEY_REF_PID))
455		{
456			if (val != NULL) r->refpid = atoi(val);
457		}
458		else if (!strcmp(key, ASL_KEY_UID))
459		{
460			if (val != NULL) r->uid = atoi(val);
461		}
462		else if (!strcmp(key, ASL_KEY_GID))
463		{
464			if (val != NULL) r->gid = atoi(val);
465		}
466		else if (!strcmp(key, ASL_KEY_LEVEL))
467		{
468			if (val != NULL) r->level = atoi(val);
469		}
470		else if (!strcmp(key, ASL_KEY_MSG))
471		{
472			if (val != NULL) r->message = asl_memory_string_retain(s, val, 1);
473		}
474		else if (!strcmp(key, ASL_KEY_SENDER_MACH_UUID))
475		{
476			if (val != NULL) r->sender_mach_uuid = asl_memory_string_retain(s, val, 1);
477		}
478		else if (!strcmp(key, ASL_KEY_FACILITY))
479		{
480			if (val != NULL) r->facility = asl_memory_string_retain(s, val, 1);
481		}
482		else if (!strcmp(key, ASL_KEY_REF_PROC))
483		{
484			if (val != NULL) r->refproc = asl_memory_string_retain(s, val, 1);
485		}
486		else if (!strcmp(key, ASL_KEY_SESSION))
487		{
488			if (val != NULL) r->session = asl_memory_string_retain(s, val, 1);
489		}
490		else if (!strcmp(key, ASL_KEY_READ_UID))
491		{
492			if (((r->flags & ASL_MSG_FLAG_READ_UID_SET) == 0) && (val != NULL))
493			{
494				r->ruid = atoi(val);
495				r->flags |= ASL_MSG_FLAG_READ_UID_SET;
496			}
497		}
498		else if (!strcmp(key, ASL_KEY_READ_GID))
499		{
500			if (((r->flags & ASL_MSG_FLAG_READ_GID_SET) == 0) && (val != NULL))
501			{
502				r->rgid = atoi(val);
503				r->flags |= ASL_MSG_FLAG_READ_GID_SET;
504			}
505		}
506		else if (!strcmp(key, ASL_KEY_OS_ACTIVITY_ID))
507		{
508			if (val != NULL) r->os_activity_id = atoll(val);
509		}
510		else if (!strcmp(key, ASL_KEY_MSG_ID))
511		{
512			/* Ignore */
513			continue;
514		}
515		else
516		{
517			k = asl_memory_string_retain(s, key, 1);
518			if (k == NULL) continue;
519
520			v = NULL;
521			if (val != NULL) v = asl_memory_string_retain(s, val, 1);
522
523			if (r->kvcount == 0)
524			{
525				r->kvlist = (mem_string_t **)calloc(2, sizeof(mem_string_t *));
526			}
527			else
528			{
529				r->kvlist = (mem_string_t **)reallocf(r->kvlist, (r->kvcount + 2) * sizeof(mem_string_t *));
530			}
531
532			if (r->kvlist == NULL)
533			{
534				asl_memory_record_clear(s, r);
535				return ASL_STATUS_NO_MEMORY;
536			}
537
538			r->kvlist[r->kvcount++] = k;
539			r->kvlist[r->kvcount++] = v;
540		}
541	}
542
543	return ASL_STATUS_OK;
544}
545
546uint32_t
547asl_memory_save(asl_memory_t *s, asl_msg_t *msg, uint64_t *mid)
548{
549	uint32_t status;
550	mem_record_t *t;
551
552	if (s == NULL) return ASL_STATUS_INVALID_STORE;
553	if (s->buffer_record == NULL) return ASL_STATUS_INVALID_STORE;
554
555	/* asl_memory_message_encode creates and caches strings */
556	status = asl_memory_message_encode(s, msg);
557	if (status != ASL_STATUS_OK) return status;
558
559	if (*mid != 0)
560	{
561		s->buffer_record->mid = *mid;
562	}
563	else
564	{
565		s->buffer_record->mid = asl_core_new_msg_id(0);
566		*mid = s->buffer_record->mid;
567	}
568
569	/* clear the first record */
570	t = s->record[s->record_first];
571	asl_memory_record_clear(s, t);
572
573	/* add the new record to the record list (swap in the buffer record) */
574	s->record[s->record_first] = s->buffer_record;
575	s->buffer_record = t;
576
577	/* record list is a circular queue */
578	s->record_first++;
579	if (s->record_first >= s->record_count) s->record_first = 0;
580
581	/* delete records if too much memory is in use */
582	while (s->curr_string_mem > s->max_string_mem)
583	{
584		asl_memory_record_clear(s, s->record[s->record_first]);
585		s->record_first++;
586		if (s->record_first >= s->record_count) s->record_first = 0;
587	}
588
589	return status;
590}
591
592/*
593 * Decodes a record structure.
594 */
595static uint32_t
596asl_memory_message_decode(asl_memory_t *s, mem_record_t *r, asl_msg_t **out)
597{
598	uint32_t i;
599	asl_msg_t *msg;
600	char tmp[64];
601	const char *key, *val;
602
603	if (s == NULL) return ASL_STATUS_INVALID_STORE;
604	if (r == NULL) return ASL_STATUS_INVALID_ARG;
605	if (out == NULL) return ASL_STATUS_INVALID_ARG;
606
607	*out = NULL;
608
609	msg = asl_msg_new(ASL_TYPE_MSG);
610	if (msg == NULL) return ASL_STATUS_NO_MEMORY;
611
612	/* Message ID */
613	snprintf(tmp, sizeof(tmp), "%llu", r->mid);
614	asl_msg_set_key_val(msg, ASL_KEY_MSG_ID, tmp);
615
616	/* Level */
617	snprintf(tmp, sizeof(tmp), "%u", r->level);
618	asl_msg_set_key_val(msg, ASL_KEY_LEVEL, tmp);
619
620	/* Time */
621	if (r->time != (uint64_t)-1)
622	{
623		snprintf(tmp, sizeof(tmp), "%llu", r->time);
624		asl_msg_set_key_val(msg, ASL_KEY_TIME, tmp);
625	}
626
627	/* Nanoseconds */
628	if (r->nano != (uint32_t)-1)
629	{
630		snprintf(tmp, sizeof(tmp), "%u", r->nano);
631		asl_msg_set_key_val(msg, ASL_KEY_TIME_NSEC, tmp);
632	}
633
634	/* Host */
635	if (r->host != NULL)
636	{
637		asl_msg_set_key_val(msg, ASL_KEY_HOST, r->host->str);
638	}
639
640	/* Sender */
641	if (r->sender != NULL)
642	{
643		asl_msg_set_key_val(msg, ASL_KEY_SENDER, r->sender->str);
644	}
645
646	/* Sender mach UUID */
647	if (r->sender_mach_uuid != NULL)
648	{
649		asl_msg_set_key_val(msg, ASL_KEY_SENDER_MACH_UUID, r->sender_mach_uuid->str);
650	}
651
652	/* Facility */
653	if (r->facility != NULL)
654	{
655		asl_msg_set_key_val(msg, ASL_KEY_FACILITY, r->facility->str);
656	}
657
658	/* Ref Proc */
659	if (r->refproc != NULL)
660	{
661		asl_msg_set_key_val(msg, ASL_KEY_REF_PROC, r->refproc->str);
662	}
663
664	/* Session */
665	if (r->session != NULL)
666	{
667		asl_msg_set_key_val(msg, ASL_KEY_SESSION, r->session->str);
668	}
669
670	/* PID */
671	if (r->pid != -1)
672	{
673		snprintf(tmp, sizeof(tmp), "%d", r->pid);
674		asl_msg_set_key_val(msg, ASL_KEY_PID, tmp);
675	}
676
677	/* REF PID */
678	if (r->refpid != 0)
679	{
680		snprintf(tmp, sizeof(tmp), "%d", r->refpid);
681		asl_msg_set_key_val(msg, ASL_KEY_REF_PID, tmp);
682	}
683
684	/* UID */
685	if (r->uid != -2)
686	{
687		snprintf(tmp, sizeof(tmp), "%d", r->uid);
688		asl_msg_set_key_val(msg, ASL_KEY_UID, tmp);
689	}
690
691	/* GID */
692	if (r->gid != -2)
693	{
694		snprintf(tmp, sizeof(tmp), "%d", r->gid);
695		asl_msg_set_key_val(msg, ASL_KEY_GID, tmp);
696	}
697
698	/* Message */
699	if (r->message != NULL)
700	{
701		asl_msg_set_key_val(msg, ASL_KEY_MSG, r->message->str);
702	}
703
704	/* ReadUID */
705	if (r->flags & ASL_MSG_FLAG_READ_UID_SET)
706	{
707		snprintf(tmp, sizeof(tmp), "%d", r->ruid);
708		asl_msg_set_key_val(msg, ASL_KEY_READ_UID, tmp);
709	}
710
711	/* ReadGID */
712	if (r->flags & ASL_MSG_FLAG_READ_GID_SET)
713	{
714		snprintf(tmp, sizeof(tmp), "%d", r->rgid);
715		asl_msg_set_key_val(msg, ASL_KEY_READ_GID, tmp);
716	}
717
718	/* OSActivityID */
719	if (r->os_activity_id != 0)
720	{
721		snprintf(tmp, sizeof(tmp), "%llu", r->os_activity_id);
722		asl_msg_set_key_val(msg, ASL_KEY_OS_ACTIVITY_ID, tmp);
723	}
724
725	/* Key - Value List */
726	for (i = 0; i < r->kvcount; i++)
727	{
728		key = NULL;
729		val = NULL;
730
731		if ((r->kvlist[i] != NULL) && (r->kvlist[i]->str != NULL)) key = r->kvlist[i]->str;
732		i++;
733		if ((r->kvlist[i] != NULL) && (r->kvlist[i]->str != NULL)) val = r->kvlist[i]->str;
734
735		if (key != NULL) asl_msg_set_key_val(msg, key, val);
736	}
737
738	*out = msg;
739	return ASL_STATUS_OK;
740}
741
742uint32_t
743asl_memory_fetch(asl_memory_t *s, uint64_t mid, asl_msg_t **msg, int32_t ruid, int32_t rgid)
744{
745	uint32_t i, status;
746
747	if (s == NULL) return ASL_STATUS_INVALID_STORE;
748	if (msg == NULL) return ASL_STATUS_INVALID_ARG;
749
750	for (i = 0; i < s->record_count; i++)
751	{
752		if (s->record[i]->mid == 0) break;
753
754		if (s->record[i]->mid == mid)
755		{
756			status = asl_core_check_access(s->record[i]->ruid, s->record[i]->rgid, ruid, rgid, s->record[i]->flags);
757			if (status != ASL_STATUS_OK) return status;
758			return asl_memory_message_decode(s, s->record[i], msg);
759		}
760	}
761
762	return ASL_STATUS_INVALID_ID;
763}
764
765static mem_record_t *
766asl_memory_query_to_record(asl_memory_t *s, asl_msg_t *q, uint32_t *type)
767{
768	mem_record_t *out;
769	uint32_t i, x;
770	uint16_t op;
771	mem_string_t *mkey, *mval;
772	const char *key, *val;
773
774	if (type == NULL) return NULL;
775
776	if (s == NULL)
777	{
778		*type = ASL_QUERY_MATCH_ERROR;
779		return NULL;
780	}
781
782	/* NULL query matches anything */
783	*type = ASL_QUERY_MATCH_TRUE;
784	if (q == NULL) return NULL;
785	if (asl_msg_count((asl_msg_t *)q) == 0) return NULL;
786
787
788	/* we can only do fast match on equality tests */
789	*type = ASL_QUERY_MATCH_SLOW;
790
791	for (x = asl_msg_fetch((asl_msg_t *)q, 0, NULL, NULL, &op); x != IndexNull; x = asl_msg_fetch((asl_msg_t *)q, x, NULL, NULL, &op))
792	{
793		if (op != ASL_QUERY_OP_EQUAL) return NULL;
794	}
795
796	out = (mem_record_t *)calloc(1, sizeof(mem_record_t));
797	if (out == NULL)
798	{
799		*type = ASL_QUERY_MATCH_ERROR;
800		return NULL;
801	}
802
803	for (x = asl_msg_fetch((asl_msg_t *)q, 0, &key, &val, &op); x != IndexNull; x = asl_msg_fetch((asl_msg_t *)q, x, &key, &val, &op))
804	{
805		if (key == NULL) continue;
806
807		else if (!strcmp(key, ASL_KEY_MSG_ID))
808		{
809			if (val == NULL) continue;
810
811			if (*type & ASL_QUERY_MATCH_MSG_ID)
812			{
813				asl_memory_record_free(s, out);
814				*type = ASL_QUERY_MATCH_SLOW;
815				return NULL;
816			}
817
818			*type |= ASL_QUERY_MATCH_MSG_ID;
819			out->mid = atoll(val);
820		}
821		else if (!strcmp(key, ASL_KEY_TIME))
822		{
823			if (val == NULL) continue;
824
825			if (*type & ASL_QUERY_MATCH_TIME)
826			{
827				asl_memory_record_free(s, out);
828				*type = ASL_QUERY_MATCH_SLOW;
829				return NULL;
830			}
831
832			*type |= ASL_QUERY_MATCH_TIME;
833			out->time = asl_core_parse_time(val, NULL);
834		}
835		else if (!strcmp(key, ASL_KEY_TIME_NSEC))
836		{
837			if (val == NULL) continue;
838
839			if (*type & ASL_QUERY_MATCH_NANO)
840			{
841				asl_memory_record_free(s, out);
842				*type = ASL_QUERY_MATCH_SLOW;
843				return NULL;
844			}
845
846			*type |= ASL_QUERY_MATCH_NANO;
847			out->nano = atoll(val);
848		}
849		else if (!strcmp(key, ASL_KEY_LEVEL))
850		{
851			if (val == NULL) continue;
852
853			if (*type & ASL_QUERY_MATCH_LEVEL)
854			{
855				asl_memory_record_free(s, out);
856				*type = ASL_QUERY_MATCH_SLOW;
857				return NULL;
858			}
859
860			*type |= ASL_QUERY_MATCH_LEVEL;
861			out->level = atoi(val);
862		}
863		else if (!strcmp(key, ASL_KEY_PID))
864		{
865			if (val == NULL) continue;
866
867			if (*type & ASL_QUERY_MATCH_PID)
868			{
869				asl_memory_record_free(s, out);
870				*type = ASL_QUERY_MATCH_SLOW;
871				return NULL;
872			}
873
874			*type |= ASL_QUERY_MATCH_PID;
875			out->pid = atoi(val);
876		}
877		else if (!strcmp(key, ASL_KEY_UID))
878		{
879			if (val == NULL) continue;
880
881			if (*type & ASL_QUERY_MATCH_UID)
882			{
883				asl_memory_record_free(s, out);
884				*type = ASL_QUERY_MATCH_SLOW;
885				return NULL;
886			}
887
888			*type |= ASL_QUERY_MATCH_UID;
889			out->uid = atoi(val);
890		}
891		else if (!strcmp(key, ASL_KEY_GID))
892		{
893			if (val == NULL) continue;
894
895			if (*type & ASL_QUERY_MATCH_GID)
896			{
897				asl_memory_record_free(s, out);
898				*type = ASL_QUERY_MATCH_SLOW;
899				return NULL;
900			}
901
902			*type |= ASL_QUERY_MATCH_GID;
903			out->gid = atoi(val);
904		}
905		else if (!strcmp(key, ASL_KEY_READ_UID))
906		{
907			if (val == NULL) continue;
908
909			if (*type & ASL_QUERY_MATCH_RUID)
910			{
911				asl_memory_record_free(s, out);
912				*type = ASL_QUERY_MATCH_SLOW;
913				return NULL;
914			}
915
916			*type |= ASL_QUERY_MATCH_RUID;
917			out->ruid = atoi(val);
918		}
919		else if (!strcmp(key, ASL_KEY_READ_GID))
920		{
921			if (val == NULL) continue;
922
923			if (*type & ASL_QUERY_MATCH_RGID)
924			{
925				asl_memory_record_free(s, out);
926				*type = ASL_QUERY_MATCH_SLOW;
927				return NULL;
928			}
929
930			*type |= ASL_QUERY_MATCH_RGID;
931			out->rgid = atoi(val);
932		}
933		else if (!strcmp(key, ASL_KEY_REF_PID))
934		{
935			if (val == NULL) continue;
936
937			if (*type & ASL_QUERY_MATCH_REF_PID)
938			{
939				asl_memory_record_free(s, out);
940				*type = ASL_QUERY_MATCH_SLOW;
941				return NULL;
942			}
943
944			*type |= ASL_QUERY_MATCH_REF_PID;
945			out->refpid = atoi(val);
946		}
947		else if (!strcmp(key, ASL_KEY_HOST))
948		{
949			if (val == NULL) continue;
950
951			if (*type & ASL_QUERY_MATCH_HOST)
952			{
953				asl_memory_record_free(s, out);
954				*type = ASL_QUERY_MATCH_SLOW;
955				return NULL;
956			}
957
958			*type |= ASL_QUERY_MATCH_HOST;
959			out->host = asl_memory_string_retain(s, val, 0);
960			if (out->host == NULL)
961			{
962				asl_memory_record_free(s, out);
963				*type = ASL_QUERY_MATCH_FALSE;
964				return NULL;
965			}
966		}
967		else if (!strcmp(key, ASL_KEY_SENDER))
968		{
969			if (val == NULL) continue;
970
971			if (*type & ASL_QUERY_MATCH_SENDER)
972			{
973				asl_memory_record_free(s, out);
974				*type = ASL_QUERY_MATCH_SLOW;
975				return NULL;
976			}
977
978			*type |= ASL_QUERY_MATCH_SENDER;
979			out->sender = asl_memory_string_retain(s, val, 0);
980			if (out->sender == NULL)
981			{
982				asl_memory_record_free(s, out);
983				*type = ASL_QUERY_MATCH_FALSE;
984				return NULL;
985			}
986		}
987		else if (!strcmp(key, ASL_KEY_SENDER_MACH_UUID))
988		{
989			if (val == NULL) continue;
990
991			if (*type & ASL_QUERY_MATCH_SMUUID)
992			{
993				asl_memory_record_free(s, out);
994				*type = ASL_QUERY_MATCH_SLOW;
995				return NULL;
996			}
997
998			*type |= ASL_QUERY_MATCH_SMUUID;
999			out->sender = asl_memory_string_retain(s, val, 0);
1000			if (out->sender_mach_uuid == NULL)
1001			{
1002				asl_memory_record_free(s, out);
1003				*type = ASL_QUERY_MATCH_FALSE;
1004				return NULL;
1005			}
1006		}
1007		else if (!strcmp(key, ASL_KEY_FACILITY))
1008		{
1009			if (val == NULL) continue;
1010
1011			if (*type & ASL_QUERY_MATCH_FACILITY)
1012			{
1013				asl_memory_record_free(s, out);
1014				*type = ASL_QUERY_MATCH_SLOW;
1015				return NULL;
1016			}
1017
1018			*type |= ASL_QUERY_MATCH_FACILITY;
1019			out->facility = asl_memory_string_retain(s, val, 0);
1020			if (out->facility == NULL)
1021			{
1022				asl_memory_record_free(s, out);
1023				*type = ASL_QUERY_MATCH_FALSE;
1024				return NULL;
1025			}
1026		}
1027		else if (!strcmp(key, ASL_KEY_MSG))
1028		{
1029			if (val == NULL) continue;
1030
1031			if (*type & ASL_QUERY_MATCH_MESSAGE)
1032			{
1033				asl_memory_record_free(s, out);
1034				*type = ASL_QUERY_MATCH_SLOW;
1035				return NULL;
1036			}
1037
1038			*type |= ASL_QUERY_MATCH_MESSAGE;
1039			out->message = asl_memory_string_retain(s, val, 0);
1040			if (out->message == NULL)
1041			{
1042				asl_memory_record_free(s, out);
1043				*type = ASL_QUERY_MATCH_FALSE;
1044				return NULL;
1045			}
1046		}
1047		else if (!strcmp(key, ASL_KEY_REF_PROC))
1048		{
1049			if (val == NULL) continue;
1050
1051			if (*type & ASL_QUERY_MATCH_REF_PROC)
1052			{
1053				asl_memory_record_free(s, out);
1054				*type = ASL_QUERY_MATCH_SLOW;
1055				return NULL;
1056			}
1057
1058			*type |= ASL_QUERY_MATCH_REF_PROC;
1059			out->refproc = asl_memory_string_retain(s, val, 0);
1060			if (out->refproc == NULL)
1061			{
1062				asl_memory_record_free(s, out);
1063				*type = ASL_QUERY_MATCH_FALSE;
1064				return NULL;
1065			}
1066		}
1067		else if (!strcmp(key, ASL_KEY_SESSION))
1068		{
1069			if (val == NULL) continue;
1070
1071			if (*type & ASL_QUERY_MATCH_SESSION)
1072			{
1073				asl_memory_record_free(s, out);
1074				*type = ASL_QUERY_MATCH_SLOW;
1075				return NULL;
1076			}
1077
1078			*type |= ASL_QUERY_MATCH_SESSION;
1079			out->session = asl_memory_string_retain(s, val, 0);
1080			if (out->session == NULL)
1081			{
1082				asl_memory_record_free(s, out);
1083				*type = ASL_QUERY_MATCH_FALSE;
1084				return NULL;
1085			}
1086		}
1087		else
1088		{
1089			mkey = asl_memory_string_retain(s, key, 0);
1090			if (mkey == NULL)
1091			{
1092				asl_memory_record_free(s, out);
1093				*type = ASL_QUERY_MATCH_FALSE;
1094				return NULL;
1095			}
1096
1097			for (i = 0; i < out->kvcount; i += 2)
1098			{
1099				if (out->kvlist[i] == mkey)
1100				{
1101					asl_memory_record_free(s, out);
1102					*type = ASL_QUERY_MATCH_SLOW;
1103					return NULL;
1104				}
1105			}
1106
1107			mval = asl_memory_string_retain(s, val, 0);
1108
1109			if (out->kvcount == 0)
1110			{
1111				out->kvlist = (mem_string_t **)calloc(2, sizeof(mem_string_t *));
1112			}
1113			else
1114			{
1115				out->kvlist = (mem_string_t **)reallocf(out->kvlist, (out->kvcount + 2) * sizeof(mem_string_t *));
1116			}
1117
1118			if (out->kvlist == NULL)
1119			{
1120				asl_memory_record_free(s, out);
1121				*type = ASL_QUERY_MATCH_ERROR;
1122				return NULL;
1123			}
1124
1125			out->kvlist[out->kvcount++] = mkey;
1126			out->kvlist[out->kvcount++] = mval;
1127		}
1128	}
1129
1130	return out;
1131}
1132
1133static uint32_t
1134asl_memory_fast_match(asl_memory_t *s, mem_record_t *r, uint32_t qtype, mem_record_t *q)
1135{
1136	uint32_t i, j;
1137
1138	if (s == NULL) return 0;
1139	if (r == NULL) return 0;
1140	if (q == NULL) return 1;
1141
1142	if ((qtype & ASL_QUERY_MATCH_MSG_ID) && (q->mid != r->mid)) return 0;
1143	if ((qtype & ASL_QUERY_MATCH_TIME) && (q->time != r->time)) return 0;
1144	if ((qtype & ASL_QUERY_MATCH_NANO) && (q->nano != r->nano)) return 0;
1145	if ((qtype & ASL_QUERY_MATCH_LEVEL) && (q->level != r->level)) return 0;
1146	if ((qtype & ASL_QUERY_MATCH_PID) && (q->pid != r->pid)) return 0;
1147	if ((qtype & ASL_QUERY_MATCH_UID) && (q->uid != r->uid)) return 0;
1148	if ((qtype & ASL_QUERY_MATCH_GID) && (q->gid != r->gid)) return 0;
1149	if ((qtype & ASL_QUERY_MATCH_RUID) && (q->ruid != r->ruid)) return 0;
1150	if ((qtype & ASL_QUERY_MATCH_RGID) && (q->rgid != r->rgid)) return 0;
1151	if ((qtype & ASL_QUERY_MATCH_REF_PID) && (q->refpid != r->refpid)) return 0;
1152	if ((qtype & ASL_QUERY_MATCH_HOST) && (q->host != r->host)) return 0;
1153	if ((qtype & ASL_QUERY_MATCH_SENDER) && (q->sender != r->sender)) return 0;
1154	if ((qtype & ASL_QUERY_MATCH_SMUUID) && (q->sender_mach_uuid != r->sender_mach_uuid)) return 0;
1155	if ((qtype & ASL_QUERY_MATCH_FACILITY) && (q->facility != r->facility)) return 0;
1156	if ((qtype & ASL_QUERY_MATCH_MESSAGE) && (q->message != r->message)) return 0;
1157	if ((qtype & ASL_QUERY_MATCH_REF_PROC) && (q->refproc != r->refproc)) return 0;
1158	if ((qtype & ASL_QUERY_MATCH_SESSION) && (q->session != r->session)) return 0;
1159
1160	for (i = 0; i < q->kvcount; i += 2)
1161	{
1162		for (j = 0; j < r->kvcount; j += 2)
1163		{
1164			if (q->kvlist[i] == r->kvlist[j])
1165			{
1166				if (q->kvlist[i + 1] == r->kvlist[j + 1]) break;
1167				return 0;
1168			}
1169		}
1170
1171		if (j >= r->kvcount) return 0;
1172	}
1173
1174	return 1;
1175}
1176
1177static uint32_t
1178asl_memory_slow_match(asl_memory_t *s, mem_record_t *r, asl_msg_t *rawq)
1179{
1180	asl_msg_t *rawm;
1181	uint32_t status;
1182
1183	rawm = NULL;
1184	status = asl_memory_message_decode(s, r, &rawm);
1185	if (status != ASL_STATUS_OK) return 0;
1186
1187	status = 0;
1188	if (asl_msg_cmp((asl_msg_t *)rawq, (asl_msg_t *)rawm) != 0) status = 1;
1189	asl_msg_release(rawm);
1190	return status;
1191}
1192
1193uint32_t
1194asl_memory_match_restricted_uuid(asl_memory_t *s, asl_msg_list_t *query, asl_msg_list_t **res, uint64_t *last_id, uint64_t start_id, uint32_t count, uint32_t duration, int32_t direction, int32_t ruid, int32_t rgid, const char *uuid_str)
1195{
1196	uint32_t status, i, where, start, j, do_match, did_match, rescount, *qtype;
1197	mem_record_t **qp;
1198	asl_msg_t *m;
1199	size_t qcount;
1200	struct timeval now, finish;
1201
1202	if (s == NULL) return ASL_STATUS_INVALID_STORE;
1203	if (res == NULL) return ASL_STATUS_INVALID_ARG;
1204
1205	qp = NULL;
1206	qtype = NULL;
1207	rescount = 0;
1208	qcount = asl_msg_list_count(query);
1209
1210	if (qcount == 0)
1211	{
1212		do_match = 0;
1213	}
1214	else
1215	{
1216		qp = (mem_record_t **)calloc(qcount, sizeof(mem_record_t *));
1217		if (qp == NULL) return ASL_STATUS_NO_MEMORY;
1218
1219		qtype = (uint32_t *)calloc(qcount, sizeof(uint32_t));
1220		if (qtype == NULL)
1221		{
1222			free(qp);
1223			return ASL_STATUS_NO_MEMORY;
1224		}
1225
1226		do_match = 0;
1227		for (i = 0; i < qcount; i++)
1228		{
1229			qp[i] = asl_memory_query_to_record(s, asl_msg_list_get_index(query, i), &(qtype[i]));
1230			if (qtype[i] == ASL_QUERY_MATCH_ERROR)
1231			{
1232				for (j = 0; j < i; j++) asl_memory_record_free(s, qp[j]);
1233				free(qp);
1234				free(qtype);
1235				return ASL_STATUS_FAILED;
1236			}
1237
1238			if (qtype[i] != ASL_QUERY_MATCH_TRUE) do_match = 1;
1239		}
1240	}
1241
1242	for (i = 0; i < s->record_count; i++)
1243	{
1244		if (direction >= 0)
1245		{
1246			where = (s->record_first + i) % s->record_count;
1247			if (s->record[where]->mid == 0) continue;
1248			if (s->record[where]->mid >= start_id) break;
1249		}
1250		else
1251		{
1252			where = ((s->record_count - (i + 1)) + s->record_first) % s->record_count;
1253			if (s->record[where]->mid == 0) continue;
1254			if (s->record[where]->mid <= start_id) break;
1255		}
1256	}
1257
1258	if (i >= s->record_count)
1259	{
1260		if (qp != NULL)
1261		{
1262			for (i = 0; i < qcount; i++) asl_memory_record_free(s, qp[i]);
1263			free(qp);
1264			free(qtype);
1265		}
1266
1267		return ASL_STATUS_OK;
1268	}
1269
1270	/* start the timer if a duration was specified */
1271	memset(&finish, 0, sizeof(struct timeval));
1272	if (duration != 0)
1273	{
1274		if (gettimeofday(&finish, NULL) == 0)
1275		{
1276			finish.tv_sec += (duration / USEC_PER_SEC);
1277			finish.tv_usec += (duration % USEC_PER_SEC);
1278			if (finish.tv_usec > USEC_PER_SEC)
1279			{
1280				finish.tv_usec -= USEC_PER_SEC;
1281				finish.tv_sec += 1;
1282			}
1283		}
1284		else
1285		{
1286			/* shouldn't happen, but if gettimeofday failed we just run without a timeout */
1287			memset(&finish, 0, sizeof(struct timeval));
1288		}
1289	}
1290
1291	start = where;
1292
1293	/*
1294	 * loop through records
1295	 */
1296	for (i = 0; i < s->record_count; i++)
1297	{
1298		status = ASL_STATUS_INVALID_ID;
1299		if (s->record[where]->mid != 0) status = asl_core_check_access(s->record[where]->ruid, s->record[where]->rgid, ruid, rgid, s->record[where]->flags);
1300
1301		if ((status == ASL_STATUS_OK) && (uuid_str != NULL))
1302		{
1303			if (s->record[where]->sender_mach_uuid == NULL) status = ASL_STATUS_INVALID_ID;
1304			else if (strcmp(s->record[where]->sender_mach_uuid->str, uuid_str) != 0) status = ASL_STATUS_INVALID_ID;
1305		}
1306
1307		if (status != ASL_STATUS_OK)
1308		{
1309			if (direction >= 0)
1310			{
1311				where++;
1312				if (where >= s->record_count) where = 0;
1313			}
1314			else
1315			{
1316				if (where == 0) where = s->record_count - 1;
1317				else where--;
1318			}
1319
1320			if (where == s->record_first) break;
1321			continue;
1322		}
1323
1324		s->record[where]->flags &= ASL_MSG_FLAG_SEARCH_CLEAR;
1325		*last_id = s->record[where]->mid;
1326		did_match = 1;
1327
1328		if (do_match != 0)
1329		{
1330			did_match = 0;
1331
1332			for (j = 0; (j < qcount) && (did_match == 0); j++)
1333			{
1334				if (qtype[j] == ASL_QUERY_MATCH_TRUE)
1335				{
1336					did_match = 1;
1337				}
1338				else if (qtype[j] == ASL_QUERY_MATCH_FALSE)
1339				{
1340					did_match = 0;
1341				}
1342				else if (qtype[j] == ASL_QUERY_MATCH_SLOW)
1343				{
1344					did_match = asl_memory_slow_match(s, s->record[where], asl_msg_list_get_index(query, j));
1345				}
1346				else
1347				{
1348					did_match = asl_memory_fast_match(s, s->record[where], qtype[j], qp[j]);
1349				}
1350			}
1351		}
1352
1353		if (did_match == 1)
1354		{
1355			s->record[where]->flags |= ASL_MSG_FLAG_SEARCH_MATCH;
1356			rescount++;
1357			if ((count != 0) && (rescount >= count)) break;
1358		}
1359
1360		/* check the timer */
1361		if ((finish.tv_sec != 0) && (gettimeofday(&now, NULL) == 0))
1362		{
1363			if ((now.tv_sec > finish.tv_sec) || ((now.tv_sec == finish.tv_sec) && (now.tv_usec > finish.tv_usec))) break;
1364		}
1365
1366		if (direction >= 0)
1367		{
1368			where++;
1369			if (where >= s->record_count) where = 0;
1370		}
1371		else
1372		{
1373			if (where == 0) where = s->record_count - 1;
1374			else where--;
1375		}
1376
1377		if (where == s->record_first) break;
1378	}
1379
1380	if (qp != NULL)
1381	{
1382		for (i = 0; i < qcount; i++) asl_memory_record_free(s, qp[i]);
1383		free(qp);
1384		free(qtype);
1385	}
1386
1387	*res = NULL;
1388	if (rescount == 0) return ASL_STATUS_OK;
1389
1390	*res = asl_msg_list_new();
1391	if (*res == NULL) return ASL_STATUS_NO_MEMORY;
1392
1393	where = start;
1394	forever
1395	{
1396		int n = 0;
1397
1398		if (s->record[where]->flags & ASL_MSG_FLAG_SEARCH_MATCH)
1399		{
1400			s->record[where]->flags &= ASL_MSG_FLAG_SEARCH_CLEAR;
1401
1402			status = asl_memory_message_decode(s, s->record[where], &m);
1403			if (status != ASL_STATUS_OK)
1404			{
1405				asl_msg_list_release(*res);
1406				*res = NULL;
1407				return status;
1408			}
1409
1410			asl_msg_list_append(*res, m);
1411			asl_msg_release(m);
1412			n++;
1413			if (n == rescount) break;
1414		}
1415
1416		if (direction >= 0)
1417		{
1418			where++;
1419			if (where >= s->record_count) where = 0;
1420		}
1421		else
1422		{
1423			if (where == 0) where = s->record_count - 1;
1424			else where--;
1425		}
1426
1427		if (where == s->record_first) break;
1428	}
1429
1430	return ASL_STATUS_OK;
1431}
1432
1433uint32_t
1434asl_memory_match(asl_memory_t *s, asl_msg_list_t *query, asl_msg_list_t **res, uint64_t *last_id, uint64_t start_id, uint32_t count, int32_t direction, int32_t ruid, int32_t rgid)
1435{
1436	return asl_memory_match_restricted_uuid(s, query, res, last_id, start_id, count, 0, direction, ruid, rgid, NULL);
1437}
1438