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