Various fixes for extent list indexing
PATCH 1/1 Various fixes for extent list indexing
We had some systems crash with this stack:
[<a00000010000cb20>] ia64_leave_kernel+0x0/0x280 [<a00000021291ca00>] xfs_bmbt_get_startoff+0x0/0x20 [xfs] [<a0000002129080b0>] xfs_bmap_last_offset+0x210/0x280 [xfs] [<a00000021295b010>] xfs_file_last_byte+0x70/0x1a0 [xfs] [<a00000021295b200>] xfs_itruncate_start+0xc0/0x1a0 [xfs] [<a0000002129935f0>] xfs_inactive_free_eofblocks+0x290/0x460 [xfs] [<a000000212998fb0>] xfs_release+0x1b0/0x240 [xfs] [<a0000002129ad930>] xfs_file_release+0x70/0xa0 [xfs] [<a000000100162ea0>] __fput+0x1a0/0x420 [<a000000100163160>] fput+0x40/0x60
I suspect what has happened here is that xfs_bmap_last_offset() has accessed the extent list without acquiring the ilock and has raced with another thread that has changed the extent list. The other thread has reduced the extent count so we've tried to access an extent beyond the end of the list.
I added some ASSERTs in xfs_iext_get_ext() and xfs_iext_idx_to_irec() to catch this and sure enough they triggered very quickly. Looking closely at the algorithm in xfs_iext_idx_to_irec(), if we try to lookup an extent beyond the end of the list the search terminates with 'low > high' and page_idx never gets updated to be an index into a specific extent buffer.
Back in xfs_iext_get_ext(), if page_idx is > 255 it is off the end of the extent buffer and potentially in unmapped memory which is how the system panicked. Some debugging in xfs_iext_get_ext() on a heavily fragmented file revealed that page_idx was 167532 while the actual count of extents in the buffer was only 254 so we accessed way outside the bounds of the extent buffer.
I put together a test program (attached) and ran it as:
# ./extent -t -l 163840000 <file>
and it found many places where we try to index an extent beyond the end of the extent list. There's code in xfs_bmapi() and xfs_bunmapi() that uses the value of if_lastex in the data fork to index an extent so it's important to make sure that field holds a sane value. The primary culprit there is xfs_bmap_del_extent() when deleting an entire extent - it leaves if_lastex as the index of the extent that was removed. If there is another extent beyond that one then if_lastex now points to that. If the removed extent was the last extent then if_lastex is now beyond the end of the list.
fs/xfs/xfs_bmap.c +17 -12
@@ -1887,7 +1887,7 @@ xfs_bmap_add_extent_hole_delay(#define SWITCH_STATE (state & MASK2(LEFT_CONTIG, RIGHT_CONTIG)) ifp =XFS_IFORK_PTR (ip,XFS_DATA_FORK ); - ep =xfs_iext_get_ext (ifp, idx); + ep =NULL ; state =0 ;ASSERT (isnullstartblock (new->br_startblock));/*
@@ -1904,6 +1904,7 @@ xfs_bmap_add_extent_hole_delay(if (STATE_SET_TEST (RIGHT_VALID , idx < ip->i_df.if_bytes / (uint )sizeof (xfs_bmbt_rec_t))) { + ep =xfs_iext_get_ext (ifp, idx);xfs_bmbt_get_all (ep, &right);STATE_SET (RIGHT_DELAY ,isnullstartblock (right.br_startblock)); }
@@ -2078,7 +2079,7 @@ xfs_bmap_add_extent_hole_real( ifp =XFS_IFORK_PTR (ip, whichfork);ASSERT (idx <= ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t)); - ep =xfs_iext_get_ext (ifp, idx); + ep =NULL ; state =0 ;/* * Check and set flags if this segment has a left neighbor.
@@ -2094,6 +2095,7 @@ xfs_bmap_add_extent_hole_real(if (STATE_SET_TEST (RIGHT_VALID , idx < ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t))) { + ep =xfs_iext_get_ext (ifp, idx);xfs_bmbt_get_all (ep, &right);STATE_SET (RIGHT_DELAY ,isnullstartblock (right.br_startblock)); }
@@ -3206,6 +3208,8 @@ xfs_bmap_del_extent(*/ XFS_BMAP_TRACE_DELETE ("3" , ip, idx,1 , whichfork);xfs_iext_remove (ifp, idx,1 ); +if (idx >= (ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t))) + idx--; ifp->if_lastex = idx;if (delay)break ;
@@ -5290,12 +5294,13 @@ xfs_bmapi(/* * Else go on to the next record. */ - ep =xfs_iext_get_ext (ifp, ++lastx); prev = got; -if (lastx >= nextents) +if (++lastx >= nextents) eof =1 ; -else +else { + ep =xfs_iext_get_ext (ifp, lastx);xfs_bmbt_get_all (ep, &got); + } } ifp->if_lastex = lastx; *nmap = n;
@@ -5723,15 +5728,15 @@ nodelete:* If not done go on to the next (previous) record. * Reset ep in case the extents array was re-alloced. */ - ep =xfs_iext_get_ext (ifp, lastx);if (bno != (xfs_fileoff_t)-1 && bno >= start) { -if (lastx >=XFS_IFORK_NEXTENTS (ip, whichfork) || -xfs_bmbt_get_startoff (ep) > bno) { -if (--lastx >=0 ) - ep =xfs_iext_get_ext (ifp, lastx); - } -if (lastx >=0 ) +if (lastx >=0 ) { + ep =xfs_iext_get_ext (ifp, lastx); +if (xfs_bmbt_get_startoff (ep) > bno) { +if (--lastx >=0 ) + ep =xfs_iext_get_ext (ifp, lastx); + }xfs_bmbt_get_all (ep, &got); + } extno++; } }
fs/xfs/xfs_inode.c +7 -4
@@ -1258,8 +1258,10 @@ xfs_file_last_byte(* necessary. */ if (ip->i_df.if_flags &XFS_IFEXTENTS ) { +xfs_ilock (ip,XFS_ILOCK_SHARED ); error =xfs_bmap_last_offset (NULL , ip, &last_block,XFS_DATA_FORK ); +xfs_iunlock (ip,XFS_ILOCK_SHARED );if (error) { last_block =0 ; }
@@ -2645,10 +2647,8 @@ xfs_iflush_fork(case XFS_DINODE_FMT_EXTENTS :ASSERT ((ifp->if_flags &XFS_IFEXTENTS ) || !(iip->ili_format.ilf_fields & extflag[whichfork])); -ASSERT ((xfs_iext_get_ext (ifp,0 ) !=NULL ) || - (ifp->if_bytes ==0 )); -ASSERT ((xfs_iext_get_ext (ifp,0 ) ==NULL ) || - (ifp->if_bytes >0 )); +ASSERT ((ifp->if_bytes ==0 ) || + (xfs_iext_get_ext (ifp,0 ) !=NULL ));if ((iip->ili_format.ilf_fields & extflag[whichfork]) && (ifp->if_bytes >0 )) {ASSERT (XFS_IFORK_NEXTENTS (ip, whichfork) >0 );
@@ -3265,6 +3265,7 @@ xfs_iext_get_ext( xfs_extnum_t idx) /* index of target extent */ {ASSERT (idx >=0 ); +ASSERT (idx < (ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t)));if ((ifp->if_flags &XFS_IFEXTIREC ) && (idx ==0 )) {return ifp->if_u1.if_ext_irec->er_extbuf; }else if (ifp->if_flags &XFS_IFEXTIREC ) {
@@ -4035,6 +4036,8 @@ xfs_iext_idx_to_irec(ASSERT (ifp->if_flags &XFS_IFEXTIREC );ASSERT (page_idx >=0 && page_idx <= ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t)); +ASSERT (page_idx < ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t) + || realloc); nlists = ifp->if_real_bytes /XFS_IEXT_BUFSZ ; erp_idx =0 ; low =0 ;
#define _LARGEFILE64_SOURCE
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#include <malloc.h>
#include <unistd.h>
#include <sys/ioctl.h>
#include <time.h>
#include <string.h>
#include <xfs/xfs.h>
#ifndef O_DIRECT
#define O_DIRECT 00040000
#endif
#define PREALLOC 1024*1024*1024
long blocks;
long *blocklist;
int blocksize;
char *buffer;
int fd;
long interval = 0;off64_t filesize = PREALLOC;
int otrunc = 0;
int odirect = 0;
int osync = 0;
int prealloc = 0;
int removefile = 0;
char *filename;
void
usage(void)
{
fprintf (stderr, "usage: extent [options] <file>\n");
fprintf (stderr, " -d use direct I/O\n");
fprintf (stderr, " -i <count> progress interval\n");
fprintf (stderr, " -l <size> file length (default %ld)\n", filesize);
fprintf (stderr, " -p preallocate file\n");
fprintf (stderr, " -r remove file after each test\n");
fprintf (stderr, " -s synchronous I/O\n");
fprintf (stderr, " -t truncate on open\n");
}void
preallocate(void)
{
struct flock f;
if (ftruncate(fd, 0) < 0) {
perror("ftruncate");
exit(1);
}
f.l_start = 0;
f.l_whence = 0;
while (f.l_start < filesize) {
f.l_len = PREALLOC;
if (f.l_len > (filesize - f.l_start))
f.l_len = filesize - f.l_start;
if (ioctl(fd, XFS_IOC_RESVSP64, &f) < 0) {
perror("fcntl");
exit(1);
}
f.l_start += f.l_len;
}
if (ftruncate(fd, filesize) < 0) {
perror("ftruncate");
exit(1);
}
}voidopen_file(char *filename)
{
fd = open(filename, O_WRONLY|O_CREAT|(otrunc ? O_TRUNC : 0)|(osync ? O_SYNC : 0)|(odirect ? O_DIRECT : 0), 0666);
if (fd < 0) {
perror("open");
exit(1);
}
}voidclose_file(void)
{
if (removefile) {
if (unlink(filename) < 0)
perror("unlink");
}
close(fd);
}voiddo_write(void)
{
int ret;
long i;
off64_t offset;
for (i = 0; i < blocks; i++) {
if (interval && (i % interval) == 0) {
printf("\rwriting record %ld of %ld, %f%%", i, blocks, ((float)i * 100) / (float)blocks);
fflush(stdout);
fdatasync(fd);
}
offset = (off64_t)blocklist[i] * (off64_t)blocksize;
if (lseek64(fd, offset, SEEK_SET) < 0)
perror("lseek");
ret = write(fd, buffer, blocksize);
if (ret < 0)
perror("write");
else if (ret < blocksize)
printf("short write\n");
}
if (interval)
printf("\rwriting record %ld of %ld, %f%%\n", i, blocks, ((float)i * 100) / (float)blocks);
}voiddo_read(void)
{
int i;
int ret;
off64_t offset = 0;
if (lseek64(fd, 0, SEEK_SET) < 0) {
perror("lseek");
exit(1);
}
for (;;) {
ret = read(fd, buffer, blocksize);
if (ret < 0) {
perror("read");
exit(1);
}
if (ret == 0)
break;
for (i = 0; i < ret; i++) {
if (buffer[i] != 'x')
printf("corruption detected at offset %ld\n", offset);
}
offset += ret;
}
}int main(int argc, char **argv)
{
struct stat buf;
long temp;
long i;
long j;
int c;
while ((c = getopt(argc, argv, "di:l:prst")) != EOF) {
switch (c) {
case 'd':
odirect = 1;
break;
case 'i':
interval = strtoul(optarg, NULL, 0);
break;
case 'l':
filesize = strtoll(optarg, NULL, 0);
break;
case 'p':
prealloc = 1;
break;
case 'r':
removefile = 1;
break;
case 's':
osync = 1;
break;
case 't':
otrunc = 1;
break;
default:
usage();
exit(1);
break;
}
}
if (optind == argc) {
usage();
exit(1);
}
filename = argv[optind];
open_file(filename);
if (fstat(fd, &buf) < 0) {
perror("fstat");
exit(1);
}
close_file();
srandom(time(NULL));
blocksize = buf.st_blksize;
blocks = filesize / blocksize;
printf("blocksize: %d\n", blocksize);
printf("blocks: %ld\n", blocks);
buffer = memalign(getpagesize(), blocksize);
if (!buffer) {
perror("malloc");
exit(1);
}
memset(buffer, 'x', blocksize);
blocklist = malloc(sizeof(blocklist[0]) * blocks);
if (!blocklist) {
perror("malloc");
exit(1);
}
open_file(filename);
if (prealloc)
preallocate();
printf("forward sequential write...\n");
for (i = 0; i < blocks; i++)
blocklist[i] = i;
do_write();
close_file();
open_file(filename);
if (prealloc)
preallocate();
printf("backward sequential write...\n");
for (i = 0; i < blocks; i++)
blocklist[i] = blocks - i - 1;
do_write();
close_file();
open_file(filename);
if (prealloc)
preallocate();
printf("stride write...\n");
for (i = 0, j = 0; i < (blocks / 2); i++, j += 2)
blocklist[i] = j;
for (j = 1; i < blocks; i++, j += 2)
blocklist[i] = j;
do_write();
close_file();
open_file(filename);
if (prealloc)
preallocate();
printf("backward stride write...\n");
for (i = 0, j = blocks - 1; i < (blocks / 2); i++, j -= 2)
blocklist[i] = j;
for (j = blocks - 2; i < blocks; i++, j -= 2)
blocklist[i] = j;
do_write();
close_file();
open_file(filename);
if (prealloc)
preallocate();
printf("inverted stride write...\n");
for (i = 0, j = 0; i < (blocks / 2); i++, j += 2)
blocklist[i] = j;
for (j = blocks - 1; i < blocks; i++, j -= 2)
blocklist[i] = j;
do_write();
close_file();
open_file(filename);
if (prealloc)
preallocate();
printf("parallel write...\n");
for (i = 0, j = 0; i < blocks; i += 2, j++)
blocklist[i] = j;
for (i = 1; i < blocks; i += 2, j++)
blocklist[i] = j;
do_write();
close_file();
open_file(filename);
if (prealloc)
preallocate();
printf("converge write...\n");
for (i = 0, j = 0; i < blocks; i += 2, j++)
blocklist[i] = j;
for (i = 1, j = blocks - 1; i < blocks; i += 2, j--)
blocklist[i] = j;
do_write();
close_file();
open_file(filename);
if (prealloc)
preallocate();
printf("diverge write...\n");
for (i = 0, j = (blocks / 2) - 1; i < blocks; i += 2, j--)
blocklist[i] = j;
for (i = 1, j = (blocks / 2); i < blocks; i += 2, j++)
blocklist[i] = j;
do_write();
close_file();
open_file(filename);
if (prealloc)
preallocate();
printf("random write...\n");
for (i = 0; i < blocks; i++)
blocklist[i] = i;
for (i = 0; i < blocks; i++) {
j = random() % blocks;
temp = blocklist[i];
blocklist[i] = blocklist[j];
blocklist[j] = temp;
}
do_write();
close_file();
free(blocklist);
free(buffer);
exit(0);
}_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs
Quoted 20 lines · Lachlan McIlroy
I suspect what has happened here is that
xfs_bmap_last_offset()has accessed the extent list without acquiring the ilock and has raced with another thread that has changed the extent list. The other thread has reduced the extent count so we've tried to access an extent beyond the end of the list.I added some ASSERTs in
xfs_iext_get_ext()andxfs_iext_idx_to_irec()to catch this and sure enough they triggered very quickly. Looking closely at the algorithm inxfs_iext_idx_to_irec(), if we try to lookup an extent beyond the end of the list the search terminates with 'low > high' andpage_idxnever gets updated to be an index into a specific extent buffer.Back in
xfs_iext_get_ext(), ifpage_idxis > 255 it is off the end of the extent buffer and potentially in unmapped memory which is how the system panicked. Some debugging inxfs_iext_get_ext()on a heavily fragmented file revealed thatpage_idxwas 167532 while the actual count of extents in the buffer was only 254 so we accessed way outside the bounds of the extent buffer.
Quoted 3 lines
I put together a test program (attached) and ran it as:
# ./extent -t -l 163840000 <file>
Can't reproduce it on my system, although I can see how it could happen from code review.
Also your patch doesn't apply for me, but I have no idea why as all the context seems correct to me.
Quoted 42 lines
and it found many places where we try to index an extent beyond the end of the extent list. There's code in
xfs_bmapi()andxfs_bunmapi()that uses the value ofif_lastexin the data fork to index an extent so it's important to make sure that field holds a sane value. The primary culprit there isxfs_bmap_del_extent()when deleting an entire extent - it leavesif_lastexas the index of the extent that was removed. If there is another extent beyond that one thenif_lastexnow points to that. If the removed extent was the last extent thenif_lastexis now beyond the end of the list.Index:
xfs-fix/fs/xfs/xfs_bmap.c
===================================================================fs/xfs/xfs_bmap.c +3
-2@@ -1887,7 +1887,7 @@ xfs_bmap_add_extent_hole_delay(#define SWITCH_STATE (state & MASK2(LEFT_CONTIG, RIGHT_CONTIG)) ifp =XFS_IFORK_PTR (ip,XFS_DATA_FORK ); - ep =xfs_iext_get_ext (ifp, idx); + ep =NULL ; state =0 ;ASSERT (isnullstartblock (new->br_startblock));/* @@ -1904,6 +1904,7 @@ xfs_bmap_add_extent_hole_delay(if (STATE_SET_TEST (RIGHT_VALID , idx < ip->i_df.if_bytes / (uint )sizeof (xfs_bmbt_rec_t))) { + ep =xfs_iext_get_ext (ifp, idx);xfs_bmbt_get_all (ep, &right);STATE_SET (RIGHT_DELAY ,isnullstartblock (right.br_startblock)); }@@ -2078,7 +2079,7 @@ xfs_bmap_add_extent_hole_real( ifp =XFS_IFORK_PTR (ip, whichfork);ASSERT (idx <= ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t)); - ep =xfs_iext_get_ext (ifp, idx); + ep =NULL ; state =0 ;/* * Check and set flags if this segment has a left neighbor.
fs/xfs/xfs_bmap.c xfs_bmap_add_extent_hole_real( · line 2101
Quoted 7 lines
fs/xfs/xfs_bmap.c +1
-0@@ -2094,6 +2095,7 @@ xfs_bmap_add_extent_hole_real(if (STATE_SET_TEST (RIGHT_VALID , idx < ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t))) { + ep =xfs_iext_get_ext (ifp, idx);xfs_bmbt_get_all (ep, &right);STATE_SET (RIGHT_DELAY ,isnullstartblock (right.br_startblock)); }
I don't quite understand the relation of these hunks to anything else in this patch, and these changes seem rather gratious to me. One cleanup in that area would be to implement the right side like the left side and just don't use an ep variable but put the xfs_iext_get_ext call directly into the argument of xfs_bmbt_get_all for the two calls per function.
fs/xfs/xfs_bmap.c xfs_bmap_del_extent( · line 3212
Quoted 6 lines
fs/xfs/xfs_bmap.c +2
-0@@ -3206,6 +3208,8 @@ xfs_bmap_del_extent(*/ XFS_BMAP_TRACE_DELETE ("3" , ip, idx,1 , whichfork);xfs_iext_remove (ifp, idx,1 ); +if (idx >= (ifp->if_bytes / (uint )sizeof (xfs_bmbt_rec_t))) + idx--;
This probably wants the comment from the introduction here, so that people know what's going on. Also the braces around the RHS and the uint cast are not needed (same for various asserts later in the patch)
fs/xfs/xfs_bmap.c nodelete: · line 5729
Quoted 3 lines
fs/xfs/xfs_bmap.c +0
-0@@ -5723,15 +5728,15 @@ nodelete:* Reset ep in case the extents array was re-alloced.
This comment isn't true anymore, is it? We should never have the extents array reallocated under us because the proper locks are held, any we now only reset ep if there is a lastx index.
fs/xfs/xfs_bmap.c nodelete: · line 5739
Quoted 9 lines
fs/xfs/xfs_bmap.c +7
-0if (bno != (xfs_fileoff_t)-1 && bno >= start) { +if (lastx >=0 ) { + ep =xfs_iext_get_ext (ifp, lastx); +if (xfs_bmbt_get_startoff (ep) > bno) { +if (--lastx >=0 ) + ep =xfs_iext_get_ext (ifp, lastx); + }xfs_bmbt_get_all (ep, &got); + }
And this stuff needs some comments, too.
_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs