1/* $NetBSD: prop_number.c,v 1.30 2016/06/28 06:47:35 pgoyette Exp $ */
2
3/*-
4 * Copyright (c) 2006 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Jason R. Thorpe.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#include <sys/rbtree.h>
33#include <prop/prop_number.h>
34#include "prop_object_impl.h"
35
36#if defined(_KERNEL)
37#include <sys/systm.h>
38#elif defined(_STANDALONE)
39#include <sys/param.h>
40#include <lib/libkern/libkern.h>
41#else
42#include <errno.h>
43#include <stdlib.h>
44#endif
45
46struct _prop_number_value {
47 union {
48 int64_t pnu_signed;
49 uint64_t pnu_unsigned;
50 } pnv_un;
51#define pnv_signed pnv_un.pnu_signed
52#define pnv_unsigned pnv_un.pnu_unsigned
53 unsigned int pnv_is_unsigned :1,
54 :31;
55};
56
57struct _prop_number {
58 struct _prop_object pn_obj;
59 struct rb_node pn_link;
60 struct _prop_number_value pn_value;
61};
62
63_PROP_POOL_INIT(_prop_number_pool, sizeof(struct _prop_number), "propnmbr")
64
65static _prop_object_free_rv_t
66 _prop_number_free(prop_stack_t, prop_object_t *);
67static bool _prop_number_externalize(
68 struct _prop_object_externalize_context *,
69 void *);
70static _prop_object_equals_rv_t
71 _prop_number_equals(prop_object_t, prop_object_t,
72 void **, void **,
73 prop_object_t *, prop_object_t *);
74
75static void _prop_number_lock(void);
76static void _prop_number_unlock(void);
77
78static const struct _prop_object_type _prop_object_type_number = {
79 .pot_type = PROP_TYPE_NUMBER,
80 .pot_free = _prop_number_free,
81 .pot_extern = _prop_number_externalize,
82 .pot_equals = _prop_number_equals,
83 .pot_lock = _prop_number_lock,
84 .pot_unlock = _prop_number_unlock,
85};
86
87#define prop_object_is_number(x) \
88 ((x) != NULL && (x)->pn_obj.po_type == &_prop_object_type_number)
89
90/*
91 * Number objects are immutable, and we are likely to have many number
92 * objects that have the same value. So, to save memory, we unique'ify
93 * numbers so we only have one copy of each.
94 */
95
96static int
97_prop_number_compare_values(const struct _prop_number_value *pnv1,
98 const struct _prop_number_value *pnv2)
99{
100
101 /* Signed numbers are sorted before unsigned numbers. */
102
103 if (pnv1->pnv_is_unsigned) {
104 if (! pnv2->pnv_is_unsigned)
105 return (1);
106 if (pnv1->pnv_unsigned < pnv2->pnv_unsigned)
107 return (-1);
108 if (pnv1->pnv_unsigned > pnv2->pnv_unsigned)
109 return (1);
110 return (0);
111 }
112
113 if (pnv2->pnv_is_unsigned)
114 return (-1);
115 if (pnv1->pnv_signed < pnv2->pnv_signed)
116 return (-1);
117 if (pnv1->pnv_signed > pnv2->pnv_signed)
118 return (1);
119 return (0);
120}
121
122static int
123/*ARGSUSED*/
124_prop_number_rb_compare_nodes(void *ctx _PROP_ARG_UNUSED,
125 const void *n1, const void *n2)
126{
127 const struct _prop_number *pn1 = n1;
128 const struct _prop_number *pn2 = n2;
129
130 return _prop_number_compare_values(&pn1->pn_value, &pn2->pn_value);
131}
132
133static int
134/*ARGSUSED*/
135_prop_number_rb_compare_key(void *ctx _PROP_ARG_UNUSED,
136 const void *n, const void *v)
137{
138 const struct _prop_number *pn = n;
139 const struct _prop_number_value *pnv = v;
140
141 return _prop_number_compare_values(&pn->pn_value, pnv);
142}
143
144static const rb_tree_ops_t _prop_number_rb_tree_ops = {
145 .rbto_compare_nodes = _prop_number_rb_compare_nodes,
146 .rbto_compare_key = _prop_number_rb_compare_key,
147 .rbto_node_offset = offsetof(struct _prop_number, pn_link),
148 .rbto_context = NULL
149};
150
151static struct rb_tree _prop_number_tree;
152_PROP_MUTEX_DECL_STATIC(_prop_number_tree_mutex)
153
154/* ARGSUSED */
155static _prop_object_free_rv_t
156_prop_number_free(prop_stack_t stack, prop_object_t *obj)
157{
158 prop_number_t pn = *obj;
159
160 rb_tree_remove_node(&_prop_number_tree, pn);
161
162 _PROP_POOL_PUT(_prop_number_pool, pn);
163
164 return (_PROP_OBJECT_FREE_DONE);
165}
166
167_PROP_ONCE_DECL(_prop_number_init_once)
168
169static int
170_prop_number_init(void)
171{
172
173 _PROP_MUTEX_INIT(_prop_number_tree_mutex);
174 rb_tree_init(&_prop_number_tree, &_prop_number_rb_tree_ops);
175 return 0;
176}
177
178static void
179_prop_number_lock(void)
180{
181 /* XXX: init necessary? */
182 _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
183 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
184}
185
186static void
187_prop_number_unlock(void)
188{
189 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
190}
191
192static bool
193_prop_number_externalize(struct _prop_object_externalize_context *ctx,
194 void *v)
195{
196 prop_number_t pn = v;
197 char tmpstr[32];
198
199 /*
200 * For unsigned numbers, we output in hex. For signed numbers,
201 * we output in decimal.
202 */
203 if (pn->pn_value.pnv_is_unsigned)
204 snprintf(tmpstr, sizeof(tmpstr), "0x%" PRIx64,
205 pn->pn_value.pnv_unsigned);
206 else
207 snprintf(tmpstr, sizeof(tmpstr), "%" PRIi64,
208 pn->pn_value.pnv_signed);
209
210 if (_prop_object_externalize_start_tag(ctx, "integer") == false ||
211 _prop_object_externalize_append_cstring(ctx, tmpstr) == false ||
212 _prop_object_externalize_end_tag(ctx, "integer") == false)
213 return (false);
214
215 return (true);
216}
217
218/* ARGSUSED */
219static _prop_object_equals_rv_t
220_prop_number_equals(prop_object_t v1, prop_object_t v2,
221 void **stored_pointer1, void **stored_pointer2,
222 prop_object_t *next_obj1, prop_object_t *next_obj2)
223{
224 prop_number_t num1 = v1;
225 prop_number_t num2 = v2;
226
227 /*
228 * There is only ever one copy of a number object at any given
229 * time, so we can reduce this to a simple pointer equality check
230 * in the common case.
231 */
232 if (num1 == num2)
233 return (_PROP_OBJECT_EQUALS_TRUE);
234
235 /*
236 * If the numbers are the same signed-ness, then we know they
237 * cannot be equal because they would have had pointer equality.
238 */
239 if (num1->pn_value.pnv_is_unsigned == num2->pn_value.pnv_is_unsigned)
240 return (_PROP_OBJECT_EQUALS_FALSE);
241
242 /*
243 * We now have one signed value and one unsigned value. We can
244 * compare them iff:
245 * - The unsigned value is not larger than the signed value
246 * can represent.
247 * - The signed value is not smaller than the unsigned value
248 * can represent.
249 */
250 if (num1->pn_value.pnv_is_unsigned) {
251 /*
252 * num1 is unsigned and num2 is signed.
253 */
254 if (num1->pn_value.pnv_unsigned > INT64_MAX)
255 return (_PROP_OBJECT_EQUALS_FALSE);
256 if (num2->pn_value.pnv_signed < 0)
257 return (_PROP_OBJECT_EQUALS_FALSE);
258 } else {
259 /*
260 * num1 is signed and num2 is unsigned.
261 */
262 if (num1->pn_value.pnv_signed < 0)
263 return (_PROP_OBJECT_EQUALS_FALSE);
264 if (num2->pn_value.pnv_unsigned > INT64_MAX)
265 return (_PROP_OBJECT_EQUALS_FALSE);
266 }
267
268 if (num1->pn_value.pnv_signed == num2->pn_value.pnv_signed)
269 return _PROP_OBJECT_EQUALS_TRUE;
270 else
271 return _PROP_OBJECT_EQUALS_FALSE;
272}
273
274static prop_number_t
275_prop_number_alloc(const struct _prop_number_value *pnv)
276{
277 prop_number_t opn, pn, rpn;
278
279 _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
280
281 /*
282 * Check to see if this already exists in the tree. If it does,
283 * we just retain it and return it.
284 */
285 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
286 opn = rb_tree_find_node(&_prop_number_tree, pnv);
287 if (opn != NULL) {
288 prop_object_retain(opn);
289 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
290 return (opn);
291 }
292 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
293
294 /*
295 * Not in the tree. Create it now.
296 */
297
298 pn = _PROP_POOL_GET(_prop_number_pool);
299 if (pn == NULL)
300 return (NULL);
301
302 _prop_object_init(&pn->pn_obj, &_prop_object_type_number);
303
304 pn->pn_value = *pnv;
305
306 /*
307 * We dropped the mutex when we allocated the new object, so
308 * we have to check again if it is in the tree.
309 */
310 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
311 opn = rb_tree_find_node(&_prop_number_tree, pnv);
312 if (opn != NULL) {
313 prop_object_retain(opn);
314 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
315 _PROP_POOL_PUT(_prop_number_pool, pn);
316 return (opn);
317 }
318 rpn = rb_tree_insert_node(&_prop_number_tree, pn);
319 _PROP_ASSERT(rpn == pn);
320 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
321 return (rpn);
322}
323
324/*
325 * prop_number_create_integer --
326 * Create a prop_number_t and initialize it with the
327 * provided integer value.
328 */
329prop_number_t
330prop_number_create_integer(int64_t val)
331{
332 struct _prop_number_value pnv;
333
334 memset(&pnv, 0, sizeof(pnv));
335 pnv.pnv_signed = val;
336 pnv.pnv_is_unsigned = false;
337
338 return (_prop_number_alloc(&pnv));
339}
340
341/*
342 * prop_number_create_unsigned_integer --
343 * Create a prop_number_t and initialize it with the
344 * provided unsigned integer value.
345 */
346prop_number_t
347prop_number_create_unsigned_integer(uint64_t val)
348{
349 struct _prop_number_value pnv;
350
351 memset(&pnv, 0, sizeof(pnv));
352 pnv.pnv_unsigned = val;
353 pnv.pnv_is_unsigned = true;
354
355 return (_prop_number_alloc(&pnv));
356}
357
358/*
359 * prop_number_copy --
360 * Copy a prop_number_t.
361 */
362prop_number_t
363prop_number_copy(prop_number_t opn)
364{
365
366 if (! prop_object_is_number(opn))
367 return (NULL);
368
369 /*
370 * Because we only ever allocate one object for any given
371 * value, this can be reduced to a simple retain operation.
372 */
373 prop_object_retain(opn);
374 return (opn);
375}
376
377/*
378 * prop_number_unsigned --
379 * Returns true if the prop_number_t has an unsigned value.
380 */
381bool
382prop_number_unsigned(prop_number_t pn)
383{
384
385 return (pn->pn_value.pnv_is_unsigned);
386}
387
388/*
389 * prop_number_size --
390 * Return the size, in bits, required to hold the value of
391 * the specified number.
392 */
393int
394prop_number_size(prop_number_t pn)
395{
396 struct _prop_number_value *pnv;
397
398 if (! prop_object_is_number(pn))
399 return (0);
400
401 pnv = &pn->pn_value;
402
403 if (pnv->pnv_is_unsigned) {
404 if (pnv->pnv_unsigned > UINT32_MAX)
405 return (64);
406 if (pnv->pnv_unsigned > UINT16_MAX)
407 return (32);
408 if (pnv->pnv_unsigned > UINT8_MAX)
409 return (16);
410 return (8);
411 }
412
413 if (pnv->pnv_signed > INT32_MAX || pnv->pnv_signed < INT32_MIN)
414 return (64);
415 if (pnv->pnv_signed > INT16_MAX || pnv->pnv_signed < INT16_MIN)
416 return (32);
417 if (pnv->pnv_signed > INT8_MAX || pnv->pnv_signed < INT8_MIN)
418 return (16);
419 return (8);
420}
421
422/*
423 * prop_number_integer_value --
424 * Get the integer value of a prop_number_t.
425 */
426int64_t
427prop_number_integer_value(prop_number_t pn)
428{
429
430 /*
431 * XXX Impossible to distinguish between "not a prop_number_t"
432 * XXX and "prop_number_t has a value of 0".
433 */
434 if (! prop_object_is_number(pn))
435 return (0);
436
437 return (pn->pn_value.pnv_signed);
438}
439
440/*
441 * prop_number_unsigned_integer_value --
442 * Get the unsigned integer value of a prop_number_t.
443 */
444uint64_t
445prop_number_unsigned_integer_value(prop_number_t pn)
446{
447
448 /*
449 * XXX Impossible to distinguish between "not a prop_number_t"
450 * XXX and "prop_number_t has a value of 0".
451 */
452 if (! prop_object_is_number(pn))
453 return (0);
454
455 return (pn->pn_value.pnv_unsigned);
456}
457
458/*
459 * prop_number_equals --
460 * Return true if two numbers are equivalent.
461 */
462bool
463prop_number_equals(prop_number_t num1, prop_number_t num2)
464{
465 if (!prop_object_is_number(num1) || !prop_object_is_number(num2))
466 return (false);
467
468 return (prop_object_equals(num1, num2));
469}
470
471/*
472 * prop_number_equals_integer --
473 * Return true if the number is equivalent to the specified integer.
474 */
475bool
476prop_number_equals_integer(prop_number_t pn, int64_t val)
477{
478
479 if (! prop_object_is_number(pn))
480 return (false);
481
482 if (pn->pn_value.pnv_is_unsigned &&
483 (pn->pn_value.pnv_unsigned > INT64_MAX || val < 0))
484 return (false);
485
486 return (pn->pn_value.pnv_signed == val);
487}
488
489/*
490 * prop_number_equals_unsigned_integer --
491 * Return true if the number is equivalent to the specified
492 * unsigned integer.
493 */
494bool
495prop_number_equals_unsigned_integer(prop_number_t pn, uint64_t val)
496{
497
498 if (! prop_object_is_number(pn))
499 return (false);
500
501 if (! pn->pn_value.pnv_is_unsigned &&
502 (pn->pn_value.pnv_signed < 0 || val > INT64_MAX))
503 return (false);
504
505 return (pn->pn_value.pnv_unsigned == val);
506}
507
508static bool
509_prop_number_internalize_unsigned(struct _prop_object_internalize_context *ctx,
510 struct _prop_number_value *pnv)
511{
512 char *cp;
513
514 _PROP_ASSERT(/*CONSTCOND*/sizeof(unsigned long long) ==
515 sizeof(uint64_t));
516
517#ifndef _KERNEL
518 errno = 0;
519#endif
520 pnv->pnv_unsigned = (uint64_t) strtoull(ctx->poic_cp, &cp, 0);
521#ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */
522 if (pnv->pnv_unsigned == UINT64_MAX && errno == ERANGE)
523 return (false);
524#endif
525 pnv->pnv_is_unsigned = true;
526 ctx->poic_cp = cp;
527
528 return (true);
529}
530
531static bool
532_prop_number_internalize_signed(struct _prop_object_internalize_context *ctx,
533 struct _prop_number_value *pnv)
534{
535 char *cp;
536
537 _PROP_ASSERT(/*CONSTCOND*/sizeof(long long) == sizeof(int64_t));
538
539#ifndef _KERNEL
540 errno = 0;
541#endif
542 pnv->pnv_signed = (int64_t) strtoll(ctx->poic_cp, &cp, 0);
543#ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */
544 if ((pnv->pnv_signed == INT64_MAX || pnv->pnv_signed == INT64_MIN) &&
545 errno == ERANGE)
546 return (false);
547#endif
548 pnv->pnv_is_unsigned = false;
549 ctx->poic_cp = cp;
550
551 return (true);
552}
553
554/*
555 * _prop_number_internalize --
556 * Parse a <number>...</number> and return the object created from
557 * the external representation.
558 */
559/* ARGSUSED */
560bool
561_prop_number_internalize(prop_stack_t stack, prop_object_t *obj,
562 struct _prop_object_internalize_context *ctx)
563{
564 struct _prop_number_value pnv;
565
566 memset(&pnv, 0, sizeof(pnv));
567
568 /* No attributes, no empty elements. */
569 if (ctx->poic_tagattr != NULL || ctx->poic_is_empty_element)
570 return (true);
571
572 /*
573 * If the first character is '-', then we treat as signed.
574 * If the first two characters are "0x" (i.e. the number is
575 * in hex), then we treat as unsigned. Otherwise, we try
576 * signed first, and if that fails (presumably due to ERANGE),
577 * then we switch to unsigned.
578 */
579 if (ctx->poic_cp[0] == '-') {
580 if (_prop_number_internalize_signed(ctx, &pnv) == false)
581 return (true);
582 } else if (ctx->poic_cp[0] == '0' && ctx->poic_cp[1] == 'x') {
583 if (_prop_number_internalize_unsigned(ctx, &pnv) == false)
584 return (true);
585 } else {
586 if (_prop_number_internalize_signed(ctx, &pnv) == false &&
587 _prop_number_internalize_unsigned(ctx, &pnv) == false)
588 return (true);
589 }
590
591 if (_prop_object_internalize_find_tag(ctx, "integer",
592 _PROP_TAG_TYPE_END) == false)
593 return (true);
594
595 *obj = _prop_number_alloc(&pnv);
596 return (true);
597}
598