aboutsummaryrefslogtreecommitdiffstats
path: root/fs/jfs/jfs_xtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/jfs/jfs_xtree.c')
-rw-r--r--fs/jfs/jfs_xtree.c263
1 files changed, 1 insertions, 262 deletions
diff --git a/fs/jfs/jfs_xtree.c b/fs/jfs/jfs_xtree.c
index a27e26c90568..d654a6458648 100644
--- a/fs/jfs/jfs_xtree.c
+++ b/fs/jfs/jfs_xtree.c
@@ -164,11 +164,8 @@ int xtLookup(struct inode *ip, s64 lstart,
164 /* is lookup offset beyond eof ? */ 164 /* is lookup offset beyond eof ? */
165 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >> 165 size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
166 JFS_SBI(ip->i_sb)->l2bsize; 166 JFS_SBI(ip->i_sb)->l2bsize;
167 if (lstart >= size) { 167 if (lstart >= size)
168 jfs_err("xtLookup: lstart (0x%lx) >= size (0x%lx)",
169 (ulong) lstart, (ulong) size);
170 return 0; 168 return 0;
171 }
172 } 169 }
173 170
174 /* 171 /*
@@ -220,264 +217,6 @@ int xtLookup(struct inode *ip, s64 lstart,
220 return rc; 217 return rc;
221} 218}
222 219
223
224/*
225 * xtLookupList()
226 *
227 * function: map a single logical extent into a list of physical extent;
228 *
229 * parameter:
230 * struct inode *ip,
231 * struct lxdlist *lxdlist, lxd list (in)
232 * struct xadlist *xadlist, xad list (in/out)
233 * int flag)
234 *
235 * coverage of lxd by xad under assumption of
236 * . lxd's are ordered and disjoint.
237 * . xad's are ordered and disjoint.
238 *
239 * return:
240 * 0: success
241 *
242 * note: a page being written (even a single byte) is backed fully,
243 * except the last page which is only backed with blocks
244 * required to cover the last byte;
245 * the extent backing a page is fully contained within an xad;
246 */
247int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
248 struct xadlist * xadlist, int flag)
249{
250 int rc = 0;
251 struct btstack btstack;
252 int cmp;
253 s64 bn;
254 struct metapage *mp;
255 xtpage_t *p;
256 int index;
257 lxd_t *lxd;
258 xad_t *xad, *pxd;
259 s64 size, lstart, lend, xstart, xend, pstart;
260 s64 llen, xlen, plen;
261 s64 xaddr, paddr;
262 int nlxd, npxd, maxnpxd;
263
264 npxd = xadlist->nxad = 0;
265 maxnpxd = xadlist->maxnxad;
266 pxd = xadlist->xad;
267
268 nlxd = lxdlist->nlxd;
269 lxd = lxdlist->lxd;
270
271 lstart = offsetLXD(lxd);
272 llen = lengthLXD(lxd);
273 lend = lstart + llen;
274
275 size = (ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
276 JFS_SBI(ip->i_sb)->l2bsize;
277
278 /*
279 * search for the xad entry covering the logical extent
280 */
281 search:
282 if (lstart >= size)
283 return 0;
284
285 if ((rc = xtSearch(ip, lstart, NULL, &cmp, &btstack, 0)))
286 return rc;
287
288 /*
289 * compute the physical extent covering logical extent
290 *
291 * N.B. search may have failed (e.g., hole in sparse file),
292 * and returned the index of the next entry.
293 */
294//map:
295 /* retrieve search result */
296 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
297
298 /* is xad on the next sibling page ? */
299 if (index == le16_to_cpu(p->header.nextindex)) {
300 if (p->header.flag & BT_ROOT)
301 goto mapend;
302
303 if ((bn = le64_to_cpu(p->header.next)) == 0)
304 goto mapend;
305
306 XT_PUTPAGE(mp);
307
308 /* get next sibling page */
309 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
310 if (rc)
311 return rc;
312
313 index = XTENTRYSTART;
314 }
315
316 xad = &p->xad[index];
317
318 /*
319 * is lxd covered by xad ?
320 */
321 compare:
322 xstart = offsetXAD(xad);
323 xlen = lengthXAD(xad);
324 xend = xstart + xlen;
325 xaddr = addressXAD(xad);
326
327 compare1:
328 if (xstart < lstart)
329 goto compare2;
330
331 /* (lstart <= xstart) */
332
333 /* lxd is NOT covered by xad */
334 if (lend <= xstart) {
335 /*
336 * get next lxd
337 */
338 if (--nlxd == 0)
339 goto mapend;
340 lxd++;
341
342 lstart = offsetLXD(lxd);
343 llen = lengthLXD(lxd);
344 lend = lstart + llen;
345 if (lstart >= size)
346 goto mapend;
347
348 /* compare with the current xad */
349 goto compare1;
350 }
351 /* lxd is covered by xad */
352 else { /* (xstart < lend) */
353
354 /* initialize new pxd */
355 pstart = xstart;
356 plen = min(lend - xstart, xlen);
357 paddr = xaddr;
358
359 goto cover;
360 }
361
362 /* (xstart < lstart) */
363 compare2:
364 /* lxd is covered by xad */
365 if (lstart < xend) {
366 /* initialize new pxd */
367 pstart = lstart;
368 plen = min(xend - lstart, llen);
369 paddr = xaddr + (lstart - xstart);
370
371 goto cover;
372 }
373 /* lxd is NOT covered by xad */
374 else { /* (xend <= lstart) */
375
376 /*
377 * get next xad
378 *
379 * linear search next xad covering lxd on
380 * the current xad page, and then tree search
381 */
382 if (index == le16_to_cpu(p->header.nextindex) - 1) {
383 if (p->header.flag & BT_ROOT)
384 goto mapend;
385
386 XT_PUTPAGE(mp);
387 goto search;
388 } else {
389 index++;
390 xad++;
391
392 /* compare with new xad */
393 goto compare;
394 }
395 }
396
397 /*
398 * lxd is covered by xad and a new pxd has been initialized
399 * (lstart <= xstart < lend) or (xstart < lstart < xend)
400 */
401 cover:
402 /* finalize pxd corresponding to current xad */
403 XT_PUTENTRY(pxd, xad->flag, pstart, plen, paddr);
404
405 if (++npxd >= maxnpxd)
406 goto mapend;
407 pxd++;
408
409 /*
410 * lxd is fully covered by xad
411 */
412 if (lend <= xend) {
413 /*
414 * get next lxd
415 */
416 if (--nlxd == 0)
417 goto mapend;
418 lxd++;
419
420 lstart = offsetLXD(lxd);
421 llen = lengthLXD(lxd);
422 lend = lstart + llen;
423 if (lstart >= size)
424 goto mapend;
425
426 /*
427 * test for old xad covering new lxd
428 * (old xstart < new lstart)
429 */
430 goto compare2;
431 }
432 /*
433 * lxd is partially covered by xad
434 */
435 else { /* (xend < lend) */
436
437 /*
438 * get next xad
439 *
440 * linear search next xad covering lxd on
441 * the current xad page, and then next xad page search
442 */
443 if (index == le16_to_cpu(p->header.nextindex) - 1) {
444 if (p->header.flag & BT_ROOT)
445 goto mapend;
446
447 if ((bn = le64_to_cpu(p->header.next)) == 0)
448 goto mapend;
449
450 XT_PUTPAGE(mp);
451
452 /* get next sibling page */
453 XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
454 if (rc)
455 return rc;
456
457 index = XTENTRYSTART;
458 xad = &p->xad[index];
459 } else {
460 index++;
461 xad++;
462 }
463
464 /*
465 * test for new xad covering old lxd
466 * (old lstart < new xstart)
467 */
468 goto compare;
469 }
470
471 mapend:
472 xadlist->nxad = npxd;
473
474//out:
475 XT_PUTPAGE(mp);
476
477 return rc;
478}
479
480
481/* 220/*
482 * xtSearch() 221 * xtSearch()
483 * 222 *