debuggers.hg

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