CVS log for src/common/lib/libprop/prop_dictionary.c

Up to [cvs.NetBSD.org] / src / common / lib / libprop

Request diff between arbitrary revisions

Keyword substitution: kv
Default branch: MAIN

Sprinkle braces around _PROP_RWLOCK_UNLOCK() in ``if'' block.
It is expanded into /* nothing */ for _STANDALONE.

proplib: Nix trailing whitespace.

s/refrences/references/

s/exisit/exist/ in comment.

Improvements to the problib(3) API:

==> Provide a much more complete set of setters and getters for different
    value types in the prop_array_util(3) and prop_dictionary_util(3)
    functions.

==> Overhaul the prop_data(3), prop_number(3), and prop_string(3) APIs
    to be easier to use and less awkwardly named,  Deprecate the old
    awkward names, and produce link-time warnings when they are referenced.

==> Deprecate mutable prop_data(3) and prop_string(3) objects.  The old
    APIs that support them still exist, but will now produce link-time
    warnings when used.

==> When the new prop_string(3) API is used, strings are internally
    de-duplicated as a memory footprint optimization.

==> Provide a rich set of bounds-checked gettter functions in and a
    corresponding set of convenience setters in the prop_number(3) API.

==> Add a new prop_bool_value(3) function that is equivalent to
    prop_bool_true(3), but aligned with the new "value" routines in
    prop_data(3), prop_string(3), and prop_number(3).

Ooops, restore accidently removed files from merge mishap

Sync with HEAD

Missed a couple of function-call renames in previous

The local copy of rb_tree code has been unused for quite some time.  So
we can just remove it, and adjust callers to use the "real" rbtree
function names.

Addresses PR lib/44090

Rebase to HEAD as of a few days ago.

sync with head.

for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.

this commit was splitted into small chunks to avoid
a limitation of cvs.  ("Protocol error: too many arguments")

Make this compilable with gcc 4.8.1 without options DIAGNOSTIC.

sync with head

Bit-un-rot the proplib portability layer.

Fix "address of a void*" vs. void* confusion.
Part of fixing PR lib/43964.

Fixes/improvements to RB-tree implementation:
1. Fix inverted node order, so that negative value from comparison operator
   would represent lower (left) node, and positive - higher (right) node.
2. Add an argument (i.e. "context"), passed to comparison operators.
3. Change rb_tree_insert_node() to return a node - either inserted one or
   already existing one.
4. Amend the interface to manipulate the actual object, instead of the
   rb_node (in a similar way as Patricia-tree interface does).
5. Update all RB-tree users accordingly.

XXX: Perhaps rename rb.h to rbtree.h, since cleaning-up..

1-3 address the PR/43488 by Jeremy Huddleston.

Passes RB-tree regression tests.
Reviewed by: matt@, christos@

Sync with HEAD.

Commit is split, to avoid a "too many arguments" protocol error.

Check if pd is not NULL before we try to lock rw lock associated with it.
This fixes proplib crash when NULL is passed to prop_dictionary_get as a
dictionary.

Get rid of locks with static initializers using once and atomic ops.
This makes proplib simplelock-free.

Pull up following revision(s) (requested by haad in ticket #1243):
	common/lib/libprop/prop_dictionary.c: revision 1.33
	common/lib/libprop/prop_number.c: revision 1.20
	common/lib/libprop/prop_object.c: revision 1.23 via patch
	common/lib/libprop/prop_object_impl.h: revision 1.28
Fix two race conditions in proplib library. In prop_dictionary and
prop_number there was small window in which was entry left in rb tree
with reference count 0 which lead to rb tree coruption when another
thread picked this up before it was released.
Add 2 new members to the prop_object_t which are used for locking/unlocking
rb tree guard mutex.
Ok by joerg@, core@, thorpej@

Pull up following revision(s) (requested by haad in ticket #1243):
	common/lib/libprop/prop_dictionary.c: revision 1.33
	common/lib/libprop/prop_number.c: revision 1.20
	common/lib/libprop/prop_object.c: revision 1.23 via patch
	common/lib/libprop/prop_object_impl.h: revision 1.28
Fix two race conditions in proplib library. In prop_dictionary and
prop_number there was small window in which was entry left in rb tree
with reference count 0 which lead to rb tree coruption when another
thread picked this up before it was released.
Add 2 new members to the prop_object_t which are used for locking/unlocking
rb tree guard mutex.
Ok by joerg@, core@, thorpej@

Pull up following revision(s) (requested by haad in ticket #150):
	common/lib/libprop/prop_dictionary.c: revision 1.33
	common/lib/libprop/prop_number.c: revision 1.20
	common/lib/libprop/prop_object.c: revision 1.23
	common/lib/libprop/prop_object_impl.h: revision 1.28
Fix two race conditions in proplib library. In prop_dictionary and
prop_number there was small window in which was entry left in rb tree with
reference count 0 which lead to rb tree coruption when another thread picked
this up before it was released.
Add 2 new members to the prop_object_t which are used for locking/unlocking
rb tree guard mutex.
Ok by joerg@, core@, thorpej@

Fix two race conditions in proplib library. In prop_dictionary and prop_number
there was small window in which was entry left in rb tree with reference
count 0 which lead to rb tree coruption when another thread picked this up
before it was released.
Add 2 new members to the prop_object_t which are used for locking/unlocking
rb tree guard mutex.

Ok by joerg@, core@, thorpej@

Sync with wrstuden-revivesa-base-2.

Fix an issue introduced with the prop_stack change: It's not a good idea to
return a 3-value enum from a function declared to return bool.  This broke
the recurse case for prop_object_equals().  Instead, declare the object type
equals routine to return a _prop_object_equals_rv_t.

Give the same treatment to the object type free routines: declare them to
return a _prop_object_free_rv_t, and consistently check those return values
againt the enum type.

Tidy up some whitespace while we're here.

Sync w/ -current. 34 merge conflicts to follow.

_prop_rb_tree_insert_node() now returns true/false to indicate if the
insertion succeeded.  Update existing usage that arranges for insertions
to always succeed to assert that they do.

sync with head

fix recursive read-lock bugs found by lockdebug and reported
by Geoff C. Wing and others.  ok'ed by Jason Thorpe.
an earlier version was tested by Sverre Froyen.
PR/38732 from oster@.

revert the recent "use trylock to hide locking errors" changes
and their associated changes, in particular, the following versions.
	prop_array.c		1.13-1.16
	prop_dictionary.c	1.25-1.28
	prop_object_impl.h	1.21-1.25
ok'ed by core@.

sync with head.

Change the argument of _PROP_RWLOCK_TRYRDLOCK() to the lock member and not
its address to be consistent with all the other macros.

Replace _prop_rwlock_tryrdlock() by a macro _PROP_RWLOCK_TRYRDLOCK().
This avoids build failures in stand alone binaries (e.g. bootloaders)
where there is no "pa_rwlock" member in the "_prop_array" structure.

prop_object_iterator_next() and prop_object_iterator_reset() were
acquiring the rwlock recursively in some paths.

Introduce _prop_rwlock_tryrdlock() and use it in these functions, so
that the rwlock is *always* acquired once, while here add some
_PROP_RWLOCK_OWNED asserts to verify.

This definitely fixes the "locking against myself" panics.

Do not acquire the rwlock recursively in prop_{array,dictionary}_iterator_reset()
when prop_{array,dictionary}_copyout_ioctl() is called.

Introduce _PROP_RWLOCK_OWNED() which is a KASSERT(rw_lock_held(lock))
and use it in those two functions, also acquire the rwlock in other
places where it is required now.

This fixes a LOCKDEBUG panic "locking against myself", as reported by
Geoff C. Wing in current-users@.

Remove clause 3 and 4 from TNF licenses

sync with head.

sync with HEAD

Actually implement prop_dictionary_make_immutable.  OK'd by thorpej@.

Include sys/simplelock.h in prop_object_impl.h.

sys/simplelock.h is required now.

sync with HEAD

Catch up on netbsd-4 as of a few days ago.

Pull up following revision(s) (requested by joerg in ticket #904):
	sbin/veriexecctl/veriexecctl.c: revision 1.29 (via patch)
	common/lib/libprop/prop_string.c: revision 1.9 (via patch)
	distrib/sets/lists/comp/mi: revision 1.1063 (via patch)
	common/lib/libprop/prop_kern.c: revision 1.8 (via patch)
	common/include/prop/prop_string.h: revision 1.2 (via patch)
	common/include/prop/prop_ingest.h: revision 1.2 (via patch)
	usr.sbin/btdevctl/btdevctl.c: revision 1.5 (via patch)
	common/lib/libprop/prop_object_impl.h: revision 1.14 (via patch)
	common/lib/libprop/prop_rb.c: revision 1.7 (via patch)
	common/include/prop/prop_array.h: revision 1.5 (via patch)
	common/lib/libprop/prop_stack.h: revision 1.1 (via patch)
	common/lib/libprop/prop_object_impl.h: revision 1.16 (via patch)
	common/lib/libprop/prop_number.3: revision 1.7 (via patch)
	common/lib/libprop/prop_stack.h: revision 1.2 (via patch)
	common/lib/libprop/prop_stack.c: revision 1.1 (via patch)
	common/lib/libprop/prop_object_impl.h: revision 1.17 (via patch)
	common/lib/libprop/prop_dictionary_util.c: revision 1.2 (via patch)
	common/lib/libprop/prop_dictionary_util.3: revision 1.2 (via patch)
	common/lib/libprop/prop_dictionary.c: revision 1.18 (via patch)
	common/lib/libprop/prop_stack.c: revision 1.2 (via patch)
	common/lib/libprop/prop_object_impl.h: revision 1.18 (via patch)
	common/lib/libprop/prop_dictionary.c: revision 1.19 (via patch)
	common/include/prop/prop_bool.h: revision 1.3 (via patch)
	common/include/prop/prop_dictionary.h: revision 1.7 (via patch)
	common/include/prop/prop_data.h: revision 1.2 (via patch)
	sys/sys/dkio.h: revision 1.14 (via patch)
	usr.sbin/btdevctl/sdp.c: revision 1.4 (via patch)
	common/include/prop/Makefile: revision 1.3 (via patch)
	common/include/prop/prop_number.h: revision 1.5 (via patch)
	common/lib/libprop/prop_object.c: revision 1.14 (via patch)
	common/lib/libprop/prop_object.c: revision 1.15 (via patch)
	common/lib/libprop/prop_object.c: revision 1.16 (via patch)
	common/lib/libprop/prop_bool.3: revision 1.3 (via patch)
	common/lib/libprop/prop_data.3: revision 1.4 (via patch)
	common/lib/libprop/prop_object.3: revision 1.6 (via patch)
	common/lib/libprop/prop_data.c: revision 1.7 (via patch)
	common/lib/libprop/prop_data.c: revision 1.8 (via patch)
	common/lib/libprop/prop_data.c: revision 1.9 (via patch)
	common/lib/libprop/prop_dictionary.c: revision 1.20 (via patch)
	usr.sbin/btdevctl/print.c: revision 1.9 (via patch)
	sbin/veriexecctl/veriexecctl_parse.y: revision 1.22 (via patch)
	common/lib/libprop/prop_number.c: revision 1.12 (via patch)
	common/include/prop/proplib.h: revision 1.5 (via patch)
	common/lib/libprop/prop_number.c: revision 1.13 (via patch)
	common/lib/libprop/prop_number.c: revision 1.14 (via patch)
	common/include/prop/prop_object.h: revision 1.5 (via patch)
	common/lib/libprop/prop_array.3: revision 1.5 (via patch)
	common/include/prop/prop_object.h: revision 1.6 (via patch)
	common/lib/libprop/prop_string.3: revision 1.4 (via patch)
	common/lib/libprop/prop_bool.c: revision 1.10 (via patch)
	common/lib/libprop/Makefile.inc: revision 1.6 (via patch)
	common/lib/libprop/prop_ingest.c: revision 1.2 (via patch)
	common/lib/libprop/prop_bool.c: revision 1.11 (via patch)
	common/lib/libprop/prop_array.c: revision 1.10 (via patch)
	common/lib/libprop/prop_ingest.3: revision 1.3 (via patch)
	common/lib/libprop/prop_bool.c: revision 1.12 (via patch)
	common/lib/libprop/prop_array.c: revision 1.11 (via patch)
	common/lib/libprop/prop_string.c: revision 1.7 (via patch)
	common/lib/libprop/prop_dictionary.3: revision 1.8 (via patch)
	common/lib/libprop/prop_array.c: revision 1.9 (via patch)
	usr.sbin/btdevctl/db.c: revision 1.4 (via patch)
	common/lib/libprop/prop_string.c: revision 1.8 (via patch)
	common/include/prop/plistref.h: revision 1.1 (via patch)
Consider '\r' to be white space. Discussed with and also kept as local
change by freza. With this change, DOS style line endings work.

boolean_t -> bool
TRUE -> true
FALSE -> false

libprop is currently using a recursive parser. While this is fine for
userland, deeply nested arrays and dictionaries can easily overflow
the kernel stack and thereby force a panic.

Fix the internalizer and prop_object_release to use a separate call
stack and alter the dictionary and array handling to not recurse on
the C stack. The default stack has an inline depth of 16 elements,
which should keep the overhead reasonable.

This issue was found by Pavel Cahyna and Jachym Holecek.

Additionally add a limit for prop_object_copyin_ioctl to prevent user
programs from temporary allocating unbound amount of kernel memory.

Allow malloc to fail so that tight loops of userland processes can't
force panics by exhausting the kernel map.

Tested with the sample exploit of Jachym, his test suite and reviewed
by himself (initial patch), Christos Zoulas and Jason Thorpe.
struct plistref does not reference other proplib data types, so split it
in its own header file to be included by dkio.h. Fixes breakage due to
pollution from proplib.h in programs which include ioctl.h. Tested and OK
by dogcow@.

Attempt at fixing build failures after proplib was converted to bool:
FALSE -> false, TRUE -> true, boolean_t -> bool, int -> bool when
appropriate, include stdbool.h . proplib.h no longer provides boolean_t,
so it is necessary to change to bool.
From Tom Spindler (dogcow@).

Avoid using unbound amount of stack frames in prop_object_equal
by using a dynamic stack as well. Reorder arguments for the internalizer
as the iteration is always present and should go before possibly
NULL arguments.
Reviewed by mjf@ and adrianp@

Avoid using unbound amount of stack frames in prop_object_equal
by using a dynamic stack as well. Reorder arguments for the internalizer
as the iteration is always present and should go before possibly
NULL arguments.

Reviewed by mjf@ and adrianp@

libprop is currently using a recursive parser. While this is fine for
userland, deeply nested arrays and dictionaries can easily overflow
the kernel stack and thereby force a panic.

Fix the internalizer and prop_object_release to use a separate call
stack and alter the dictionary and array handling to not recurse on
the C stack. The default stack has an inline depth of 16 elements,
which should keep the overhead reasonable.

This issue was found by Pavel Cahyna and Jachym Holecek.

Additionally add a limit for prop_object_copyin_ioctl to prevent user
programs from temporary allocating unbound amount of kernel memory.
Allow malloc to fail so that tight loops of userland processes can't
force panics by exhausting the kernel map.

Tested with the sample exploit of Jachym, his test suite and reviewed
by himself (initial patch), Christos Zoulas and Jason Thorpe.

boolean_t -> bool
TRUE -> true
FALSE -> false

prop_array_internalize and prop_dictionary_internalize are basically the
same code. Refactor it into _prop_generic_internalize, which gets passed
the second-level tag.

- Add prop_dictionary_all_keys().  Takes a snapshot of a dictionary's
  keys and returns them in an array.  This effectively allows a caller
  to mutate a dictionary while iterating over it (really, you iterate
  over the array of keys instead of the dictionary itself).
- Add a slew of utility functions that make it more convenient (in some
  circumstances, anyway) to get/set values in a dictionary.

file prop_dictionary.c was added on branch newlock2 on 2006-10-26 05:02:13 +0000

- Add prop_dictionary_all_keys().  Takes a snapshot of a dictionary's
  keys and returns them in an array.  This effectively allows a caller
  to mutate a dictionary while iterating over it (really, you iterate
  over the array of keys instead of the dictionary itself).
- Add a slew of utility functions that make it more convenient (in some
  circumstances, anyway) to get/set values in a dictionary.

Backout size_t casts - lint has been fixed.

Sprinkle a few size_t casts to avoid conversion warnings.

- Add a reader-writer lock to array and dictionary objects that ensures that
  the data structure is internally consistent in the face of multiple threads
  accessing it concurrently.  This is not designed to provide application-
  level semantic consistency; applications are responsible for that locking
  protocol should it be necessary.
- Rename _PROP_MUTEX_DECL() to _PROP_MUTEX_DECL_STATIC().

Adapt Matt Thomas's red-black tree implementation for use in proplib.  This
has a significant code size savings over <sys/tree.h>.

Also change prop_number_t to store all number objects in an r-b tree,
only ever allocating one object for any given number (we can do this
because numbers are immutable).  This results in significant run-time
memory savings.

Pull up following revision(s) (requested by riz in ticket #87):
	common/lib/libprop/prop_dictionary.c: revision 1.10
Add a workaround for GCC -Wuninitialized, similar to the prop_array.c
workaround, and properly marked with XXXGCC -Wuninitialized.

Pull up following revision(s) (requested by thorpej in ticket #51):
	common/lib/libprop/prop_dictionary.c: revision 1.11
	common/lib/libprop/prop_number.c: revision 1.5
	common/lib/libprop/prop_bool.c: revision 1.5
	common/lib/libprop/prop_data.c: revision 1.4
	common/lib/libprop/prop_string.c: revision 1.4
	common/lib/libprop/prop_array.c: revision 1.6
Also guard object accessors against NULL (like we do foreign object
types)
so that apps can use this construct safely:
	obj = prop_dictionary_get(dict, "value");
	if (! prop_number_equals_integer(obj, 5)) {
		...
	}
Suggested by Iain Hibbert.

Pull up following revision(s) (requested by thorpej in ticket #43):
	common/include/prop/prop_ingest.h: revision 1.1
	common/lib/libprop/prop_number.c: revision 1.4
	common/include/prop/prop_array.h: revision 1.3
	common/lib/libprop/prop_object_impl.h: revision 1.4
	common/include/prop/prop_dictionary.h: revision 1.4
	distrib/sets/lists/comp/mi: revision 1.911
	common/include/prop/Makefile: revision 1.2
	common/lib/libprop/prop_bool.c: revision 1.4
	distrib/sets/lists/base/shl.mi: revision 1.365
	common/lib/libprop/prop_data.c: revision 1.3
	lib/libprop/shlib_version: revision 1.4
	lib/libprop/Makefile: revision 1.6
	common/lib/libprop/prop_object.c: revision 1.4
	common/lib/libprop/prop_object.3: revision 1.4
	common/include/prop/proplib.h: revision 1.3
	common/lib/libprop/Makefile.inc: revision 1.3
	common/include/prop/prop_object.h: revision 1.4
	common/lib/libprop/prop_array.c: revision 1.4
	common/lib/libprop/prop_array.3: revision 1.4
	common/lib/libprop/prop_string.c: revision 1.3
	common/lib/libprop/prop_dictionary.3: revision 1.4
	common/lib/libprop/prop_ingest.c: revision 1.1
	common/lib/libprop/prop_ingest.3: revision 1.1
	common/lib/libprop/prop_dictionary.c: revision 1.9
Several changes to proplib:
- Arrays can now be externalized and internalized in the same way
  dictionaries can.
- Add new "externalize to file" and "internalize from file" functions
  to make reading a property list from a file and writing a property
  list to a file more convenient.
- Many assertions in the object implementations are gone.  Instead,
  calling an accessor for one object type with a different object type
  as an argument will return a suitable "invalid" value.
- prop_object_type() now returns a new PROP_TYPE_UNKNOWN value if called
  with a NULL object.
- Externalized property lists now contain a reference to the Apple XML
  plist DTD.
- Add a new prop_ingest(3) facility, which provides a convenient way to
  translate a dictionary into an arbitrary binary representation.

Also guard object accessors against NULL (like we do foreign object types)
so that apps can use this construct safely:

	obj = prop_dictionary_get(dict, "value");
	if (! prop_number_equals_integer(obj, 5)) {
		...
	}

Suggested by Iain Hibbert.

Add a workaround for GCC -Wuninitialized, similar to the prop_array.c
workaround, and properly marked with XXXGCC -Wuninitialized.

Several changes to proplib:
- Arrays can now be externalized and internalized in the same way
  dictionaries can.
- Add new "externalize to file" and "internalize from file" functions
  to make reading a property list from a file and writing a property
  list to a file more convenient.
- Many assertions in the object implementations are gone.  Instead,
  calling an accessor for one object type with a different object type
  as an argument will return a suitable "invalid" value.
- prop_object_type() now returns a new PROP_TYPE_UNKNOWN value if called
  with a NULL object.
- Externalized property lists now contain a reference to the Apple XML
  plist DTD.
- Add a new prop_ingest(3) facility, which provides a convenient way to
  translate a dictionary into an arbitrary binary representation.

Use a red-black tree to unique'ify the dictionary key symbols, rather than
a sorted array.  Using a tree puts the linkage into the key symbol itself,
allowing us to avoid having to allocate memory with a mutex held.

remove unused variable that broke build

Keep a table of unique dictionary keysyms.  This way, if we have 200 devices
with the "fw-path" property, we only have one copy of the "fw-path" string
as a dictionary key.

More cleanup.

Minor cleanup.

- Add prop_array_equals(), prop_dictionary_equals(), and
  prop_dictionary_keysym_equals(), and prop_object_equals() functions.
- Use realloc() where it makes sense.  There will be more changes in this
  area.
- Add a _prop_object_type structure that is used internally to keep
  information about the object types.  Decreases the footprint of the
  objects slightly by replacing several pointers with just one.

In _prop_dictionary_alloc(), explicitly set pd->pd_flags to zero
instead of leaving random garbage in there.
Should we just use "memset(pd, 0, sizeof(*pd));" instead?

Fixes boot problems on evbppc/WALNUT with new proplib.

Initial commit of proplib, a library for manipulating property lists and
converting to/from an XML external representation (based on Apple XML
property lists).  Works in the kernel and user space.