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