ia64/xen-unstable

view xen/common/lib.c @ 17062:0769835cf50f

x86 shadow: Reduce scope of shadow lock.

emulate_map_dest doesn't require holding lock, since
only shadow related operation possibly involved is to
remove shadow which is less frequent and can acquire
lock inside. Rest are either guest table walk or
per-vcpu monitor table manipulation

Signed-off-by Kevin Tian <kevin.tian@intel.com>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Feb 14 10:33:12 2008 +0000 (2008-02-14)
parents e7ceed4ebcd9
children 50634c215234
line source
2 #include <xen/ctype.h>
3 #include <xen/lib.h>
4 #include <xen/types.h>
5 #include <asm/byteorder.h>
7 /* for ctype.h */
8 unsigned char _ctype[] = {
9 _C,_C,_C,_C,_C,_C,_C,_C, /* 0-7 */
10 _C,_C|_S,_C|_S,_C|_S,_C|_S,_C|_S,_C,_C, /* 8-15 */
11 _C,_C,_C,_C,_C,_C,_C,_C, /* 16-23 */
12 _C,_C,_C,_C,_C,_C,_C,_C, /* 24-31 */
13 _S|_SP,_P,_P,_P,_P,_P,_P,_P, /* 32-39 */
14 _P,_P,_P,_P,_P,_P,_P,_P, /* 40-47 */
15 _D,_D,_D,_D,_D,_D,_D,_D, /* 48-55 */
16 _D,_D,_P,_P,_P,_P,_P,_P, /* 56-63 */
17 _P,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U, /* 64-71 */
18 _U,_U,_U,_U,_U,_U,_U,_U, /* 72-79 */
19 _U,_U,_U,_U,_U,_U,_U,_U, /* 80-87 */
20 _U,_U,_U,_P,_P,_P,_P,_P, /* 88-95 */
21 _P,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L, /* 96-103 */
22 _L,_L,_L,_L,_L,_L,_L,_L, /* 104-111 */
23 _L,_L,_L,_L,_L,_L,_L,_L, /* 112-119 */
24 _L,_L,_L,_P,_P,_P,_P,_C, /* 120-127 */
25 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 128-143 */
26 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 144-159 */
27 _S|_SP,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P, /* 160-175 */
28 _P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P,_P, /* 176-191 */
29 _U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U,_U, /* 192-207 */
30 _U,_U,_U,_U,_U,_U,_U,_P,_U,_U,_U,_U,_U,_U,_U,_L, /* 208-223 */
31 _L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L,_L, /* 224-239 */
32 _L,_L,_L,_L,_L,_L,_L,_P,_L,_L,_L,_L,_L,_L,_L,_L}; /* 240-255 */
34 /*
35 * A couple of 64 bit operations ported from FreeBSD.
36 * The code within the '#if BITS_PER_LONG == 32' block below, and no other
37 * code in this file, is distributed under the following licensing terms
38 * This is the modified '3-clause' BSD license with the obnoxious
39 * advertising clause removed, as permitted by University of California.
40 *
41 * Copyright (c) 1992, 1993
42 * The Regents of the University of California. All rights reserved.
43 *
44 * This software was developed by the Computer Systems Engineering group
45 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
46 * contributed to Berkeley.
47 *
48 * Redistribution and use in source and binary forms, with or without
49 * modification, are permitted provided that the following conditions
50 * are met:
51 * 1. Redistributions of source code must retain the above copyright
52 * notice, this list of conditions and the following disclaimer.
53 * 2. Redistributions in binary form must reproduce the above copyright
54 * notice, this list of conditions and the following disclaimer in the
55 * documentation and/or other materials provided with the distribution.
56 * 3. Neither the name of the University nor the names of its contributors
57 * may be used to endorse or promote products derived from this software
58 * without specific prior written permission.
59 *
60 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
61 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
62 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
63 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
64 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
65 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
66 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
67 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
68 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
69 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
70 * SUCH DAMAGE.
71 */
72 #if BITS_PER_LONG == 32
74 /*
75 * Depending on the desired operation, we view a `long long' (aka quad_t) in
76 * one or more of the following formats.
77 */
78 union uu {
79 s64 q; /* as a (signed) quad */
80 s64 uq; /* as an unsigned quad */
81 long sl[2]; /* as two signed longs */
82 unsigned long ul[2]; /* as two unsigned longs */
83 };
85 #ifdef __BIG_ENDIAN
86 #define _QUAD_HIGHWORD 0
87 #define _QUAD_LOWWORD 1
88 #else /* __LITTLE_ENDIAN */
89 #define _QUAD_HIGHWORD 1
90 #define _QUAD_LOWWORD 0
91 #endif
93 /*
94 * Define high and low longwords.
95 */
96 #define H _QUAD_HIGHWORD
97 #define L _QUAD_LOWWORD
99 /*
100 * Total number of bits in a quad_t and in the pieces that make it up.
101 * These are used for shifting, and also below for halfword extraction
102 * and assembly.
103 */
104 #define CHAR_BIT 8 /* number of bits in a char */
105 #define QUAD_BITS (sizeof(s64) * CHAR_BIT)
106 #define LONG_BITS (sizeof(long) * CHAR_BIT)
107 #define HALF_BITS (sizeof(long) * CHAR_BIT / 2)
109 /*
110 * Extract high and low shortwords from longword, and move low shortword of
111 * longword to upper half of long, i.e., produce the upper longword of
112 * ((quad_t)(x) << (number_of_bits_in_long/2)). (`x' must actually be u_long.)
113 *
114 * These are used in the multiply code, to split a longword into upper
115 * and lower halves, and to reassemble a product as a quad_t, shifted left
116 * (sizeof(long)*CHAR_BIT/2).
117 */
118 #define HHALF(x) ((x) >> HALF_BITS)
119 #define LHALF(x) ((x) & ((1 << HALF_BITS) - 1))
120 #define LHUP(x) ((x) << HALF_BITS)
122 /*
123 * Multiprecision divide. This algorithm is from Knuth vol. 2 (2nd ed),
124 * section 4.3.1, pp. 257--259.
125 */
126 #define B (1 << HALF_BITS) /* digit base */
128 /* Combine two `digits' to make a single two-digit number. */
129 #define COMBINE(a, b) (((u_long)(a) << HALF_BITS) | (b))
131 /* select a type for digits in base B */
132 typedef u_long digit;
134 /*
135 * Shift p[0]..p[len] left `sh' bits, ignoring any bits that
136 * `fall out' the left (there never will be any such anyway).
137 * We may assume len >= 0. NOTE THAT THIS WRITES len+1 DIGITS.
138 */
139 static void shl(register digit *p, register int len, register int sh)
140 {
141 register int i;
143 for (i = 0; i < len; i++)
144 p[i] = LHALF(p[i] << sh) | (p[i + 1] >> (HALF_BITS - sh));
145 p[i] = LHALF(p[i] << sh);
146 }
148 /*
149 * __qdivrem(u, v, rem) returns u/v and, optionally, sets *rem to u%v.
150 *
151 * We do this in base 2-sup-HALF_BITS, so that all intermediate products
152 * fit within u_long. As a consequence, the maximum length dividend and
153 * divisor are 4 `digits' in this base (they are shorter if they have
154 * leading zeros).
155 */
156 u64 __qdivrem(u64 uq, u64 vq, u64 *arq)
157 {
158 union uu tmp;
159 digit *u, *v, *q;
160 register digit v1, v2;
161 u_long qhat, rhat, t;
162 int m, n, d, j, i;
163 digit uspace[5], vspace[5], qspace[5];
165 /*
166 * Take care of special cases: divide by zero, and u < v.
167 */
168 if (vq == 0) {
169 /* divide by zero. */
170 static volatile const unsigned int zero = 0;
172 tmp.ul[H] = tmp.ul[L] = 1 / zero;
173 if (arq)
174 *arq = uq;
175 return (tmp.q);
176 }
177 if (uq < vq) {
178 if (arq)
179 *arq = uq;
180 return (0);
181 }
182 u = &uspace[0];
183 v = &vspace[0];
184 q = &qspace[0];
186 /*
187 * Break dividend and divisor into digits in base B, then
188 * count leading zeros to determine m and n. When done, we
189 * will have:
190 * u = (u[1]u[2]...u[m+n]) sub B
191 * v = (v[1]v[2]...v[n]) sub B
192 * v[1] != 0
193 * 1 < n <= 4 (if n = 1, we use a different division algorithm)
194 * m >= 0 (otherwise u < v, which we already checked)
195 * m + n = 4
196 * and thus
197 * m = 4 - n <= 2
198 */
199 tmp.uq = uq;
200 u[0] = 0;
201 u[1] = HHALF(tmp.ul[H]);
202 u[2] = LHALF(tmp.ul[H]);
203 u[3] = HHALF(tmp.ul[L]);
204 u[4] = LHALF(tmp.ul[L]);
205 tmp.uq = vq;
206 v[1] = HHALF(tmp.ul[H]);
207 v[2] = LHALF(tmp.ul[H]);
208 v[3] = HHALF(tmp.ul[L]);
209 v[4] = LHALF(tmp.ul[L]);
210 for (n = 4; v[1] == 0; v++) {
211 if (--n == 1) {
212 u_long rbj; /* r*B+u[j] (not root boy jim) */
213 digit q1, q2, q3, q4;
215 /*
216 * Change of plan, per exercise 16.
217 * r = 0;
218 * for j = 1..4:
219 * q[j] = floor((r*B + u[j]) / v),
220 * r = (r*B + u[j]) % v;
221 * We unroll this completely here.
222 */
223 t = v[2]; /* nonzero, by definition */
224 q1 = u[1] / t;
225 rbj = COMBINE(u[1] % t, u[2]);
226 q2 = rbj / t;
227 rbj = COMBINE(rbj % t, u[3]);
228 q3 = rbj / t;
229 rbj = COMBINE(rbj % t, u[4]);
230 q4 = rbj / t;
231 if (arq)
232 *arq = rbj % t;
233 tmp.ul[H] = COMBINE(q1, q2);
234 tmp.ul[L] = COMBINE(q3, q4);
235 return (tmp.q);
236 }
237 }
239 /*
240 * By adjusting q once we determine m, we can guarantee that
241 * there is a complete four-digit quotient at &qspace[1] when
242 * we finally stop.
243 */
244 for (m = 4 - n; u[1] == 0; u++)
245 m--;
246 for (i = 4 - m; --i >= 0;)
247 q[i] = 0;
248 q += 4 - m;
250 /*
251 * Here we run Program D, translated from MIX to C and acquiring
252 * a few minor changes.
253 *
254 * D1: choose multiplier 1 << d to ensure v[1] >= B/2.
255 */
256 d = 0;
257 for (t = v[1]; t < B / 2; t <<= 1)
258 d++;
259 if (d > 0) {
260 shl(&u[0], m + n, d); /* u <<= d */
261 shl(&v[1], n - 1, d); /* v <<= d */
262 }
263 /*
264 * D2: j = 0.
265 */
266 j = 0;
267 v1 = v[1]; /* for D3 -- note that v[1..n] are constant */
268 v2 = v[2]; /* for D3 */
269 do {
270 register digit uj0, uj1, uj2;
272 /*
273 * D3: Calculate qhat (\^q, in TeX notation).
274 * Let qhat = min((u[j]*B + u[j+1])/v[1], B-1), and
275 * let rhat = (u[j]*B + u[j+1]) mod v[1].
276 * While rhat < B and v[2]*qhat > rhat*B+u[j+2],
277 * decrement qhat and increase rhat correspondingly.
278 * Note that if rhat >= B, v[2]*qhat < rhat*B.
279 */
280 uj0 = u[j + 0]; /* for D3 only -- note that u[j+...] change */
281 uj1 = u[j + 1]; /* for D3 only */
282 uj2 = u[j + 2]; /* for D3 only */
283 if (uj0 == v1) {
284 qhat = B;
285 rhat = uj1;
286 goto qhat_too_big;
287 } else {
288 u_long nn = COMBINE(uj0, uj1);
289 qhat = nn / v1;
290 rhat = nn % v1;
291 }
292 while (v2 * qhat > COMBINE(rhat, uj2)) {
293 qhat_too_big:
294 qhat--;
295 if ((rhat += v1) >= B)
296 break;
297 }
298 /*
299 * D4: Multiply and subtract.
300 * The variable `t' holds any borrows across the loop.
301 * We split this up so that we do not require v[0] = 0,
302 * and to eliminate a final special case.
303 */
304 for (t = 0, i = n; i > 0; i--) {
305 t = u[i + j] - v[i] * qhat - t;
306 u[i + j] = LHALF(t);
307 t = (B - HHALF(t)) & (B - 1);
308 }
309 t = u[j] - t;
310 u[j] = LHALF(t);
311 /*
312 * D5: test remainder.
313 * There is a borrow if and only if HHALF(t) is nonzero;
314 * in that (rare) case, qhat was too large (by exactly 1).
315 * Fix it by adding v[1..n] to u[j..j+n].
316 */
317 if (HHALF(t)) {
318 qhat--;
319 for (t = 0, i = n; i > 0; i--) { /* D6: add back. */
320 t += u[i + j] + v[i];
321 u[i + j] = LHALF(t);
322 t = HHALF(t);
323 }
324 u[j] = LHALF(u[j] + t);
325 }
326 q[j] = qhat;
327 } while (++j <= m); /* D7: loop on j. */
329 /*
330 * If caller wants the remainder, we have to calculate it as
331 * u[m..m+n] >> d (this is at most n digits and thus fits in
332 * u[m+1..m+n], but we may need more source digits).
333 */
334 if (arq) {
335 if (d) {
336 for (i = m + n; i > m; --i)
337 u[i] = (u[i] >> d) |
338 LHALF(u[i - 1] << (HALF_BITS - d));
339 u[i] = 0;
340 }
341 tmp.ul[H] = COMBINE(uspace[1], uspace[2]);
342 tmp.ul[L] = COMBINE(uspace[3], uspace[4]);
343 *arq = tmp.q;
344 }
346 tmp.ul[H] = COMBINE(qspace[1], qspace[2]);
347 tmp.ul[L] = COMBINE(qspace[3], qspace[4]);
348 return (tmp.q);
349 }
351 /*
352 * Divide two signed quads.
353 * Truncates towards zero, as required by C99.
354 */
355 s64 __divdi3(s64 a, s64 b)
356 {
357 u64 ua, ub, uq;
358 int neg = (a < 0) ^ (b < 0);
359 ua = (a < 0) ? -(u64)a : a;
360 ub = (b < 0) ? -(u64)b : b;
361 uq = __qdivrem(ua, ub, (u64 *)0);
362 return (neg ? -uq : uq);
363 }
366 /*
367 * Divide two unsigned quads.
368 */
369 u64 __udivdi3(u64 a, u64 b)
370 {
371 return __qdivrem(a, b, (u64 *)0);
372 }
374 /*
375 * Remainder of unsigned quad division
376 */
377 u64 __umoddi3(u64 a, u64 b)
378 {
379 u64 rem;
380 __qdivrem(a, b, &rem);
381 return rem;
382 }
384 /*
385 * Remainder of signed quad division.
386 * Truncates towards zero, as required by C99:
387 * 11 % 5 = 1
388 * -11 % 5 = -1
389 * 11 % -5 = 1
390 * -11 % -5 = 1
391 */
392 s64 __moddi3(s64 a, s64 b)
393 {
394 u64 ua, ub, urem;
395 int neg = (a < 0);
396 ua = neg ? -(u64)a : a;
397 ub = (b < 0) ? -(u64)b : b;
398 __qdivrem(ua, ub, &urem);
399 return (neg ? -urem : urem);
400 }
402 #endif /* BITS_PER_LONG == 32 */
404 unsigned long long parse_size_and_unit(const char *s, const char **ps)
405 {
406 unsigned long long ret;
407 const char *s1;
409 ret = simple_strtoull(s, &s1, 0);
411 switch ( *s1 )
412 {
413 case 'G': case 'g':
414 ret <<= 10;
415 case 'M': case 'm':
416 ret <<= 10;
417 case 'K': case 'k':
418 ret <<= 10;
419 case 'B': case 'b':
420 s1++;
421 break;
422 default:
423 ret <<= 10; /* default to kB */
424 break;
425 }
427 if ( ps != NULL )
428 *ps = s1;
430 return ret;
431 }
433 /*
434 * Local variables:
435 * mode: C
436 * c-set-style: "BSD"
437 * c-basic-offset: 4
438 * tab-width: 4
439 * indent-tabs-mode: nil
440 * End:
441 */