debuggers.hg

annotate xen/common/sort.c @ 22855:1d1eec7e1fb4

xl: Perform minimal validation of virtual disk file while parsing config file

This patch performs some very basic validation on the virtual disk
file passed through the config file. This validation ensures that we
don't go too far with the initialization like spawn qemu and more
while there could be some potentially fundamental issues.

[ Patch fixed up to work with PHYSTYPE_EMPTY 22808:6ec61438713a -iwj ]

Signed-off-by: Kamala Narasimhan <kamala.narasimhan@citrix.com>
Acked-by: Ian Jackson <ian.jackson@eu.citrix.com>
Signed-off-by: Ian Jackson <ian.jackson@eu.citrix.com>
Committed-by: Ian Jackson <ian.jackson@eu.citrix.com>
author Kamala Narasimhan <kamala.narasimhan@gmail.com>
date Tue Jan 25 18:09:49 2011 +0000 (2011-01-25)
parents ef30046259f0
children
rev   line source
keir@22673 1 /*
keir@22673 2 * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
keir@22673 3 *
keir@22673 4 * Jan 23 2005 Matt Mackall <mpm@selenic.com>
keir@22673 5 */
keir@22673 6
keir@22673 7 #include <xen/types.h>
keir@22673 8
keir@22673 9 static void u32_swap(void *a, void *b, int size)
keir@22673 10 {
keir@22673 11 u32 t = *(u32 *)a;
keir@22673 12 *(u32 *)a = *(u32 *)b;
keir@22673 13 *(u32 *)b = t;
keir@22673 14 }
keir@22673 15
keir@22673 16 static void generic_swap(void *a, void *b, int size)
keir@22673 17 {
keir@22673 18 char t;
keir@22673 19
keir@22673 20 do {
keir@22673 21 t = *(char *)a;
keir@22673 22 *(char *)a++ = *(char *)b;
keir@22673 23 *(char *)b++ = t;
keir@22673 24 } while ( --size > 0 );
keir@22673 25 }
keir@22673 26
keir@22673 27 /*
keir@22673 28 * sort - sort an array of elements
keir@22673 29 * @base: pointer to data to sort
keir@22673 30 * @num: number of elements
keir@22673 31 * @size: size of each element
keir@22673 32 * @cmp: pointer to comparison function
keir@22673 33 * @swap: pointer to swap function or NULL
keir@22673 34 *
keir@22673 35 * This function does a heapsort on the given array. You may provide a
keir@22673 36 * swap function optimized to your element type.
keir@22673 37 *
keir@22673 38 * Sorting time is O(n log n) both on average and worst-case. While
keir@22673 39 * qsort is about 20% faster on average, it suffers from exploitable
keir@22673 40 * O(n*n) worst-case behavior and extra memory requirements that make
keir@22673 41 * it less suitable for kernel use.
keir@22673 42 */
keir@22673 43
keir@22673 44 void sort(void *base, size_t num, size_t size,
keir@22673 45 int (*cmp)(const void *, const void *),
keir@22673 46 void (*swap)(void *, void *, int size))
keir@22673 47 {
keir@22673 48 /* pre-scale counters for performance */
keir@22673 49 int i = (num/2) * size, n = num * size, c, r;
keir@22673 50
keir@22673 51 if (!swap)
keir@22673 52 swap = (size == 4 ? u32_swap : generic_swap);
keir@22673 53
keir@22673 54 /* heapify */
keir@22673 55 for ( ; i >= 0; i -= size )
keir@22673 56 {
keir@22673 57 for ( r = i; r * 2 < n; r = c )
keir@22673 58 {
keir@22673 59 c = r * 2;
keir@22673 60 if ( (c < n - size) && (cmp(base + c, base + c + size) < 0) )
keir@22673 61 c += size;
keir@22673 62 if ( cmp(base + r, base + c) >= 0 )
keir@22673 63 break;
keir@22673 64 swap(base + r, base + c, size);
keir@22673 65 }
keir@22673 66 }
keir@22673 67
keir@22673 68 /* sort */
keir@22673 69 for ( i = n - size; i >= 0; i -= size )
keir@22673 70 {
keir@22673 71 swap(base, base + i, size);
keir@22673 72 for ( r = 0; r * 2 < i; r = c )
keir@22673 73 {
keir@22673 74 c = r * 2;
keir@22673 75 if ( (c < i - size) && (cmp(base + c, base + c + size) < 0) )
keir@22673 76 c += size;
keir@22673 77 if ( cmp(base + r, base + c) >= 0 )
keir@22673 78 break;
keir@22673 79 swap(base + r, base + c, size);
keir@22673 80 }
keir@22673 81 }
keir@22673 82 }