[PATCH][BZ #16009] fix memory handling in strxfrm_l

[Leonhard Holz <leonhard dot holz at web dot de>]

Hello,

this patch solves bug #16009 by implementing an additional path in 
strxfrm that does not depend on caching the weight and rule indices.

In detail the following changed:

* The old main loop was factored out of strxfrm_l into the function 
do_xfrm_cached to be able to alternativly use the non-caching version 
do_xfrm.

* strxfrm_l allocates a a fixed size array on the stack. If this is not 
sufficiant to store the weight and rule indices, the non-caching path is 
taken. As the cache size is not dependent on the input there can be no 
problems with integer overflows or stack allocations greater than 
__MAX_ALLOCA_CUTOFF. Note that malloc-ing is not possible because the 
definition of strxfrm does not allow an oom errorhandling.

* The uncached path determines the weight and rule index for every char 
and for every pass again. Handling of backward sequences needs a special 
threatment, I found no way to implement it without allocation. This is 
now done by pushing the backward sequence on the stack within a single 
linked list that can later easily be traversed backwards (but not 
free'd) and avoids the problem of stack allocations beyond 
__MAX_ALLOCA_CUTOFF. Here again, malloc is not possible.

* Passing all the locale data array by array resulted in very long 
parameter lists, so I introduced a structure that holds them.

* Checking for zero src string has been moved a bit upwards, it is 
before the locale data initialization now.

* To verify that the non-caching path works correct I added a test run 
to localedata/sort-test.sh & localedata/xfrm-test.c where all strings 
are patched up with spaces so that they are too large for the caching path.

make tests && make xcheck report no additional errors. Unfortunately the 
diff of strxfrm_l.c is a bit messy, it looks factoring out the main loop 
was too much for git. :|

Leonhard

2014-11-29  Leonhard Holz <leonhard.holz@web.de>

        [BZ #16009]
	* string/strxfrm_l.c (STRXFRM): Allocate fixed size cache
	for weights and rules. Use do_xfrm_cached if data fits in
	cache, do_xfrm otherwise. Moved former main loop to...
	* (do_xfrm_cached): New function.
	* (do_xfrm): Non-caching version of do_xfrm_cached. Uses
	find_idx, find_position and stack_push.
	* (find_idx): New function.
	* (find_position): Likewise.
	* (stack_push): New macro.
	* localedata/sort-test.sh: Added test run for do_xfrm.
	* localedata/xfrm-test.c (main): Added command line
	option -nocache to run the test with strings that are
	too large for the STRXFRM cache.

Attachment: strxfrm_l.c.diff
Description: Text document

Attachment: sort-test.sh.diff
Description: Text document

Attachment: xfrm-test.c.diff
Description: Text document