]> git.saurik.com Git - apple/syslog.git/blob - aslcommon/asl_memory.c
5bd090cd3967d5e2240178e19dc5a4664f915330
[apple/syslog.git] / aslcommon / asl_memory.c
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
43 uint32_t
44 asl_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
91 uint32_t
92 asl_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
129 uint32_t
130 asl_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
174 static mem_string_t *
175 mem_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 */
201 static uint32_t
202 asl_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 */
260 static mem_string_t *
261 asl_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
319 static uint32_t
320 asl_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 */
368 static void
369 asl_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
390 static void
391 asl_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 */
401 static uint32_t
402 asl_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
546 uint32_t
547 asl_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 */
595 static uint32_t
596 asl_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
742 uint32_t
743 asl_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
765 static mem_record_t *
766 asl_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
1133 static uint32_t
1134 asl_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
1177 static uint32_t
1178 asl_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
1193 uint32_t
1194 asl_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
1433 uint32_t
1434 asl_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 }