// SPDX-License-Identifier: GPL-2.0
|
/*
|
* linux/fs/hpfs/dnode.c
|
*
|
* Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
|
*
|
* handling directory dnode tree - adding, deleteing & searching for dirents
|
*/
|
|
#include "hpfs_fn.h"
|
|
static loff_t get_pos(struct dnode *d, struct hpfs_dirent *fde)
|
{
|
struct hpfs_dirent *de;
|
struct hpfs_dirent *de_end = dnode_end_de(d);
|
int i = 1;
|
for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
|
if (de == fde) return ((loff_t) le32_to_cpu(d->self) << 4) | (loff_t)i;
|
i++;
|
}
|
pr_info("%s(): not_found\n", __func__);
|
return ((loff_t)le32_to_cpu(d->self) << 4) | (loff_t)1;
|
}
|
|
int hpfs_add_pos(struct inode *inode, loff_t *pos)
|
{
|
struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
|
int i = 0;
|
loff_t **ppos;
|
|
if (hpfs_inode->i_rddir_off)
|
for (; hpfs_inode->i_rddir_off[i]; i++)
|
if (hpfs_inode->i_rddir_off[i] == pos)
|
return 0;
|
if (!(i&0x0f)) {
|
ppos = kmalloc_array(i + 0x11, sizeof(loff_t *), GFP_NOFS);
|
if (!ppos) {
|
pr_err("out of memory for position list\n");
|
return -ENOMEM;
|
}
|
if (hpfs_inode->i_rddir_off) {
|
memcpy(ppos, hpfs_inode->i_rddir_off, i * sizeof(loff_t));
|
kfree(hpfs_inode->i_rddir_off);
|
}
|
hpfs_inode->i_rddir_off = ppos;
|
}
|
hpfs_inode->i_rddir_off[i] = pos;
|
hpfs_inode->i_rddir_off[i + 1] = NULL;
|
return 0;
|
}
|
|
void hpfs_del_pos(struct inode *inode, loff_t *pos)
|
{
|
struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
|
loff_t **i, **j;
|
|
if (!hpfs_inode->i_rddir_off) goto not_f;
|
for (i = hpfs_inode->i_rddir_off; *i; i++) if (*i == pos) goto fnd;
|
goto not_f;
|
fnd:
|
for (j = i + 1; *j; j++) ;
|
*i = *(j - 1);
|
*(j - 1) = NULL;
|
if (j - 1 == hpfs_inode->i_rddir_off) {
|
kfree(hpfs_inode->i_rddir_off);
|
hpfs_inode->i_rddir_off = NULL;
|
}
|
return;
|
not_f:
|
/*pr_warn("position pointer %p->%08x not found\n",
|
pos, (int)*pos);*/
|
return;
|
}
|
|
static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
|
loff_t p1, loff_t p2)
|
{
|
struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
|
loff_t **i;
|
|
if (!hpfs_inode->i_rddir_off) return;
|
for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
|
return;
|
}
|
|
static void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
|
{
|
if (*p == f) *p = t;
|
}
|
|
/*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
|
{
|
if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
|
}*/
|
|
static void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
|
{
|
if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
|
int n = (*p & 0x3f) + c;
|
if (n > 0x3f)
|
pr_err("%s(): %08x + %d\n",
|
__func__, (int)*p, (int)c >> 8);
|
else
|
*p = (*p & ~0x3f) | n;
|
}
|
}
|
|
static void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
|
{
|
if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
|
int n = (*p & 0x3f) - c;
|
if (n < 1)
|
pr_err("%s(): %08x - %d\n",
|
__func__, (int)*p, (int)c >> 8);
|
else
|
*p = (*p & ~0x3f) | n;
|
}
|
}
|
|
static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
|
{
|
struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL;
|
de_end = dnode_end_de(d);
|
for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
|
deee = dee; dee = de;
|
}
|
return deee;
|
}
|
|
static struct hpfs_dirent *dnode_last_de(struct dnode *d)
|
{
|
struct hpfs_dirent *de, *de_end, *dee = NULL;
|
de_end = dnode_end_de(d);
|
for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
|
dee = de;
|
}
|
return dee;
|
}
|
|
static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
|
{
|
struct hpfs_dirent *de;
|
if (!(de = dnode_last_de(d))) {
|
hpfs_error(s, "set_last_pointer: empty dnode %08x", le32_to_cpu(d->self));
|
return;
|
}
|
if (hpfs_sb(s)->sb_chk) {
|
if (de->down) {
|
hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
|
le32_to_cpu(d->self), de_down_pointer(de));
|
return;
|
}
|
if (le16_to_cpu(de->length) != 32) {
|
hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", le32_to_cpu(d->self));
|
return;
|
}
|
}
|
if (ptr) {
|
le32_add_cpu(&d->first_free, 4);
|
if (le32_to_cpu(d->first_free) > 2048) {
|
hpfs_error(s, "set_last_pointer: too long dnode %08x", le32_to_cpu(d->self));
|
le32_add_cpu(&d->first_free, -4);
|
return;
|
}
|
de->length = cpu_to_le16(36);
|
de->down = 1;
|
*(__le32 *)((char *)de + 32) = cpu_to_le32(ptr);
|
}
|
}
|
|
/* Add an entry to dnode and don't care if it grows over 2048 bytes */
|
|
struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d,
|
const unsigned char *name,
|
unsigned namelen, secno down_ptr)
|
{
|
struct hpfs_dirent *de;
|
struct hpfs_dirent *de_end = dnode_end_de(d);
|
unsigned d_size = de_size(namelen, down_ptr);
|
for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
|
int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last);
|
if (!c) {
|
hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, le32_to_cpu(d->self));
|
return NULL;
|
}
|
if (c < 0) break;
|
}
|
memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
|
memset(de, 0, d_size);
|
if (down_ptr) {
|
*(__le32 *)((char *)de + d_size - 4) = cpu_to_le32(down_ptr);
|
de->down = 1;
|
}
|
de->length = cpu_to_le16(d_size);
|
de->not_8x3 = hpfs_is_name_long(name, namelen);
|
de->namelen = namelen;
|
memcpy(de->name, name, namelen);
|
le32_add_cpu(&d->first_free, d_size);
|
return de;
|
}
|
|
/* Delete dirent and don't care about its subtree */
|
|
static void hpfs_delete_de(struct super_block *s, struct dnode *d,
|
struct hpfs_dirent *de)
|
{
|
if (de->last) {
|
hpfs_error(s, "attempt to delete last dirent in dnode %08x", le32_to_cpu(d->self));
|
return;
|
}
|
d->first_free = cpu_to_le32(le32_to_cpu(d->first_free) - le16_to_cpu(de->length));
|
memmove(de, de_next_de(de), le32_to_cpu(d->first_free) + (char *)d - (char *)de);
|
}
|
|
static void fix_up_ptrs(struct super_block *s, struct dnode *d)
|
{
|
struct hpfs_dirent *de;
|
struct hpfs_dirent *de_end = dnode_end_de(d);
|
dnode_secno dno = le32_to_cpu(d->self);
|
for (de = dnode_first_de(d); de < de_end; de = de_next_de(de))
|
if (de->down) {
|
struct quad_buffer_head qbh;
|
struct dnode *dd;
|
if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
|
if (le32_to_cpu(dd->up) != dno || dd->root_dnode) {
|
dd->up = cpu_to_le32(dno);
|
dd->root_dnode = 0;
|
hpfs_mark_4buffers_dirty(&qbh);
|
}
|
hpfs_brelse4(&qbh);
|
}
|
}
|
}
|
|
/* Add an entry to dnode and do dnode splitting if required */
|
|
static int hpfs_add_to_dnode(struct inode *i, dnode_secno dno,
|
const unsigned char *name, unsigned namelen,
|
struct hpfs_dirent *new_de, dnode_secno down_ptr)
|
{
|
struct quad_buffer_head qbh, qbh1, qbh2;
|
struct dnode *d, *ad, *rd, *nd = NULL;
|
dnode_secno adno, rdno;
|
struct hpfs_dirent *de;
|
struct hpfs_dirent nde;
|
unsigned char *nname;
|
int h;
|
int pos;
|
struct buffer_head *bh;
|
struct fnode *fnode;
|
int c1, c2 = 0;
|
if (!(nname = kmalloc(256, GFP_NOFS))) {
|
pr_err("out of memory, can't add to dnode\n");
|
return 1;
|
}
|
go_up:
|
if (namelen >= 256) {
|
hpfs_error(i->i_sb, "%s(): namelen == %d", __func__, namelen);
|
kfree(nd);
|
kfree(nname);
|
return 1;
|
}
|
if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
|
kfree(nd);
|
kfree(nname);
|
return 1;
|
}
|
go_up_a:
|
if (hpfs_sb(i->i_sb)->sb_chk)
|
if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
|
hpfs_brelse4(&qbh);
|
kfree(nd);
|
kfree(nname);
|
return 1;
|
}
|
if (le32_to_cpu(d->first_free) + de_size(namelen, down_ptr) <= 2048) {
|
loff_t t;
|
copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
|
t = get_pos(d, de);
|
for_all_poss(i, hpfs_pos_ins, t, 1);
|
for_all_poss(i, hpfs_pos_subst, 4, t);
|
for_all_poss(i, hpfs_pos_subst, 5, t + 1);
|
hpfs_mark_4buffers_dirty(&qbh);
|
hpfs_brelse4(&qbh);
|
kfree(nd);
|
kfree(nname);
|
return 0;
|
}
|
if (!nd) if (!(nd = kmalloc(0x924, GFP_NOFS))) {
|
/* 0x924 is a max size of dnode after adding a dirent with
|
max name length. We alloc this only once. There must
|
not be any error while splitting dnodes, otherwise the
|
whole directory, not only file we're adding, would
|
be lost. */
|
pr_err("out of memory for dnode splitting\n");
|
hpfs_brelse4(&qbh);
|
kfree(nname);
|
return 1;
|
}
|
memcpy(nd, d, le32_to_cpu(d->first_free));
|
copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de);
|
for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1);
|
h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10;
|
if (!(ad = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &adno, &qbh1))) {
|
hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
|
hpfs_brelse4(&qbh);
|
kfree(nd);
|
kfree(nname);
|
return 1;
|
}
|
i->i_size += 2048;
|
i->i_blocks += 4;
|
pos = 1;
|
for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) {
|
copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de);
|
for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos);
|
pos++;
|
}
|
copy_de(new_de = &nde, de);
|
memcpy(nname, de->name, de->namelen);
|
name = nname;
|
namelen = de->namelen;
|
for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4);
|
down_ptr = adno;
|
set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
|
de = de_next_de(de);
|
memmove((char *)nd + 20, de, le32_to_cpu(nd->first_free) + (char *)nd - (char *)de);
|
le32_add_cpu(&nd->first_free, -((char *)de - (char *)nd - 20));
|
memcpy(d, nd, le32_to_cpu(nd->first_free));
|
for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos);
|
fix_up_ptrs(i->i_sb, ad);
|
if (!d->root_dnode) {
|
ad->up = d->up;
|
dno = le32_to_cpu(ad->up);
|
hpfs_mark_4buffers_dirty(&qbh);
|
hpfs_brelse4(&qbh);
|
hpfs_mark_4buffers_dirty(&qbh1);
|
hpfs_brelse4(&qbh1);
|
goto go_up;
|
}
|
if (!(rd = hpfs_alloc_dnode(i->i_sb, le32_to_cpu(d->up), &rdno, &qbh2))) {
|
hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
|
hpfs_brelse4(&qbh);
|
hpfs_brelse4(&qbh1);
|
kfree(nd);
|
kfree(nname);
|
return 1;
|
}
|
i->i_size += 2048;
|
i->i_blocks += 4;
|
rd->root_dnode = 1;
|
rd->up = d->up;
|
if (!(fnode = hpfs_map_fnode(i->i_sb, le32_to_cpu(d->up), &bh))) {
|
hpfs_free_dnode(i->i_sb, rdno);
|
hpfs_brelse4(&qbh);
|
hpfs_brelse4(&qbh1);
|
hpfs_brelse4(&qbh2);
|
kfree(nd);
|
kfree(nname);
|
return 1;
|
}
|
fnode->u.external[0].disk_secno = cpu_to_le32(rdno);
|
mark_buffer_dirty(bh);
|
brelse(bh);
|
hpfs_i(i)->i_dno = rdno;
|
d->up = ad->up = cpu_to_le32(rdno);
|
d->root_dnode = ad->root_dnode = 0;
|
hpfs_mark_4buffers_dirty(&qbh);
|
hpfs_brelse4(&qbh);
|
hpfs_mark_4buffers_dirty(&qbh1);
|
hpfs_brelse4(&qbh1);
|
qbh = qbh2;
|
set_last_pointer(i->i_sb, rd, dno);
|
dno = rdno;
|
d = rd;
|
goto go_up_a;
|
}
|
|
/*
|
* Add an entry to directory btree.
|
* I hate such crazy directory structure.
|
* It's easy to read but terrible to write.
|
* I wrote this directory code 4 times.
|
* I hope, now it's finally bug-free.
|
*/
|
|
int hpfs_add_dirent(struct inode *i,
|
const unsigned char *name, unsigned namelen,
|
struct hpfs_dirent *new_de)
|
{
|
struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
|
struct dnode *d;
|
struct hpfs_dirent *de, *de_end;
|
struct quad_buffer_head qbh;
|
dnode_secno dno;
|
int c;
|
int c1, c2 = 0;
|
dno = hpfs_inode->i_dno;
|
down:
|
if (hpfs_sb(i->i_sb)->sb_chk)
|
if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
|
if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
|
de_end = dnode_end_de(d);
|
for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
|
if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
|
hpfs_brelse4(&qbh);
|
return -1;
|
}
|
if (c < 0) {
|
if (de->down) {
|
dno = de_down_pointer(de);
|
hpfs_brelse4(&qbh);
|
goto down;
|
}
|
break;
|
}
|
}
|
hpfs_brelse4(&qbh);
|
if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
|
c = 1;
|
goto ret;
|
}
|
c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
|
ret:
|
return c;
|
}
|
|
/*
|
* Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
|
* Return the dnode we moved from (to be checked later if it's empty)
|
*/
|
|
static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
|
{
|
dnode_secno dno, ddno;
|
dnode_secno chk_up = to;
|
struct dnode *dnode;
|
struct quad_buffer_head qbh;
|
struct hpfs_dirent *de, *nde;
|
int a;
|
loff_t t;
|
int c1, c2 = 0;
|
dno = from;
|
while (1) {
|
if (hpfs_sb(i->i_sb)->sb_chk)
|
if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
|
return 0;
|
if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0;
|
if (hpfs_sb(i->i_sb)->sb_chk) {
|
if (le32_to_cpu(dnode->up) != chk_up) {
|
hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x",
|
dno, chk_up, le32_to_cpu(dnode->up));
|
hpfs_brelse4(&qbh);
|
return 0;
|
}
|
chk_up = dno;
|
}
|
if (!(de = dnode_last_de(dnode))) {
|
hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
|
hpfs_brelse4(&qbh);
|
return 0;
|
}
|
if (!de->down) break;
|
dno = de_down_pointer(de);
|
hpfs_brelse4(&qbh);
|
}
|
while (!(de = dnode_pre_last_de(dnode))) {
|
dnode_secno up = le32_to_cpu(dnode->up);
|
hpfs_brelse4(&qbh);
|
hpfs_free_dnode(i->i_sb, dno);
|
i->i_size -= 2048;
|
i->i_blocks -= 4;
|
for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5);
|
if (up == to) return to;
|
if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0;
|
if (dnode->root_dnode) {
|
hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to);
|
hpfs_brelse4(&qbh);
|
return 0;
|
}
|
de = dnode_last_de(dnode);
|
if (!de || !de->down) {
|
hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno);
|
hpfs_brelse4(&qbh);
|
return 0;
|
}
|
le32_add_cpu(&dnode->first_free, -4);
|
le16_add_cpu(&de->length, -4);
|
de->down = 0;
|
hpfs_mark_4buffers_dirty(&qbh);
|
dno = up;
|
}
|
t = get_pos(dnode, de);
|
for_all_poss(i, hpfs_pos_subst, t, 4);
|
for_all_poss(i, hpfs_pos_subst, t + 1, 5);
|
if (!(nde = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
|
hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted");
|
hpfs_brelse4(&qbh);
|
return 0;
|
}
|
memcpy(nde, de, le16_to_cpu(de->length));
|
ddno = de->down ? de_down_pointer(de) : 0;
|
hpfs_delete_de(i->i_sb, dnode, de);
|
set_last_pointer(i->i_sb, dnode, ddno);
|
hpfs_mark_4buffers_dirty(&qbh);
|
hpfs_brelse4(&qbh);
|
a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
|
kfree(nde);
|
if (a) return 0;
|
return dno;
|
}
|
|
/*
|
* Check if a dnode is empty and delete it from the tree
|
* (chkdsk doesn't like empty dnodes)
|
*/
|
|
static void delete_empty_dnode(struct inode *i, dnode_secno dno)
|
{
|
struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
|
struct quad_buffer_head qbh;
|
struct dnode *dnode;
|
dnode_secno down, up, ndown;
|
int p;
|
struct hpfs_dirent *de;
|
int c1, c2 = 0;
|
try_it_again:
|
if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return;
|
if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return;
|
if (le32_to_cpu(dnode->first_free) > 56) goto end;
|
if (le32_to_cpu(dnode->first_free) == 52 || le32_to_cpu(dnode->first_free) == 56) {
|
struct hpfs_dirent *de_end;
|
int root = dnode->root_dnode;
|
up = le32_to_cpu(dnode->up);
|
de = dnode_first_de(dnode);
|
down = de->down ? de_down_pointer(de) : 0;
|
if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) {
|
hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno);
|
goto end;
|
}
|
hpfs_brelse4(&qbh);
|
hpfs_free_dnode(i->i_sb, dno);
|
i->i_size -= 2048;
|
i->i_blocks -= 4;
|
if (root) {
|
struct fnode *fnode;
|
struct buffer_head *bh;
|
struct dnode *d1;
|
struct quad_buffer_head qbh1;
|
if (hpfs_sb(i->i_sb)->sb_chk)
|
if (up != i->i_ino) {
|
hpfs_error(i->i_sb,
|
"bad pointer to fnode, dnode %08x, pointing to %08x, should be %08lx",
|
dno, up,
|
(unsigned long)i->i_ino);
|
return;
|
}
|
if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
|
d1->up = cpu_to_le32(up);
|
d1->root_dnode = 1;
|
hpfs_mark_4buffers_dirty(&qbh1);
|
hpfs_brelse4(&qbh1);
|
}
|
if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
|
fnode->u.external[0].disk_secno = cpu_to_le32(down);
|
mark_buffer_dirty(bh);
|
brelse(bh);
|
}
|
hpfs_inode->i_dno = down;
|
for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
|
return;
|
}
|
if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
|
p = 1;
|
de_end = dnode_end_de(dnode);
|
for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
|
if (de->down) if (de_down_pointer(de) == dno) goto fnd;
|
hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
|
goto end;
|
fnd:
|
for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
|
if (!down) {
|
de->down = 0;
|
le16_add_cpu(&de->length, -4);
|
le32_add_cpu(&dnode->first_free, -4);
|
memmove(de_next_de(de), (char *)de_next_de(de) + 4,
|
(char *)dnode + le32_to_cpu(dnode->first_free) - (char *)de_next_de(de));
|
} else {
|
struct dnode *d1;
|
struct quad_buffer_head qbh1;
|
*(dnode_secno *) ((void *) de + le16_to_cpu(de->length) - 4) = down;
|
if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
|
d1->up = cpu_to_le32(up);
|
hpfs_mark_4buffers_dirty(&qbh1);
|
hpfs_brelse4(&qbh1);
|
}
|
}
|
} else {
|
hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, le32_to_cpu(dnode->first_free));
|
goto end;
|
}
|
|
if (!de->last) {
|
struct hpfs_dirent *de_next = de_next_de(de);
|
struct hpfs_dirent *de_cp;
|
struct dnode *d1;
|
struct quad_buffer_head qbh1;
|
if (!de_next->down) goto endm;
|
ndown = de_down_pointer(de_next);
|
if (!(de_cp = kmalloc(le16_to_cpu(de->length), GFP_NOFS))) {
|
pr_err("out of memory for dtree balancing\n");
|
goto endm;
|
}
|
memcpy(de_cp, de, le16_to_cpu(de->length));
|
hpfs_delete_de(i->i_sb, dnode, de);
|
hpfs_mark_4buffers_dirty(&qbh);
|
hpfs_brelse4(&qbh);
|
for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
|
for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
|
if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
|
d1->up = cpu_to_le32(ndown);
|
hpfs_mark_4buffers_dirty(&qbh1);
|
hpfs_brelse4(&qbh1);
|
}
|
hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
|
/*pr_info("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n",
|
up, ndown, down, dno);*/
|
dno = up;
|
kfree(de_cp);
|
goto try_it_again;
|
} else {
|
struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
|
struct hpfs_dirent *de_cp;
|
struct dnode *d1;
|
struct quad_buffer_head qbh1;
|
dnode_secno dlp;
|
if (!de_prev) {
|
hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
|
hpfs_mark_4buffers_dirty(&qbh);
|
hpfs_brelse4(&qbh);
|
dno = up;
|
goto try_it_again;
|
}
|
if (!de_prev->down) goto endm;
|
ndown = de_down_pointer(de_prev);
|
if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
|
struct hpfs_dirent *del = dnode_last_de(d1);
|
dlp = del->down ? de_down_pointer(del) : 0;
|
if (!dlp && down) {
|
if (le32_to_cpu(d1->first_free) > 2044) {
|
if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
|
pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n");
|
pr_err("terminating balancing operation\n");
|
}
|
hpfs_brelse4(&qbh1);
|
goto endm;
|
}
|
if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
|
pr_err("unbalanced dnode tree, see hpfs.txt 4 more info\n");
|
pr_err("goin'on\n");
|
}
|
le16_add_cpu(&del->length, 4);
|
del->down = 1;
|
le32_add_cpu(&d1->first_free, 4);
|
}
|
if (dlp && !down) {
|
le16_add_cpu(&del->length, -4);
|
del->down = 0;
|
le32_add_cpu(&d1->first_free, -4);
|
} else if (down)
|
*(__le32 *) ((void *) del + le16_to_cpu(del->length) - 4) = cpu_to_le32(down);
|
} else goto endm;
|
if (!(de_cp = kmalloc(le16_to_cpu(de_prev->length), GFP_NOFS))) {
|
pr_err("out of memory for dtree balancing\n");
|
hpfs_brelse4(&qbh1);
|
goto endm;
|
}
|
hpfs_mark_4buffers_dirty(&qbh1);
|
hpfs_brelse4(&qbh1);
|
memcpy(de_cp, de_prev, le16_to_cpu(de_prev->length));
|
hpfs_delete_de(i->i_sb, dnode, de_prev);
|
if (!de_prev->down) {
|
le16_add_cpu(&de_prev->length, 4);
|
de_prev->down = 1;
|
le32_add_cpu(&dnode->first_free, 4);
|
}
|
*(__le32 *) ((void *) de_prev + le16_to_cpu(de_prev->length) - 4) = cpu_to_le32(ndown);
|
hpfs_mark_4buffers_dirty(&qbh);
|
hpfs_brelse4(&qbh);
|
for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
|
for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
|
if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
|
d1->up = cpu_to_le32(ndown);
|
hpfs_mark_4buffers_dirty(&qbh1);
|
hpfs_brelse4(&qbh1);
|
}
|
hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
|
dno = up;
|
kfree(de_cp);
|
goto try_it_again;
|
}
|
endm:
|
hpfs_mark_4buffers_dirty(&qbh);
|
end:
|
hpfs_brelse4(&qbh);
|
}
|
|
|
/* Delete dirent from directory */
|
|
int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
|
struct quad_buffer_head *qbh, int depth)
|
{
|
struct dnode *dnode = qbh->data;
|
dnode_secno down = 0;
|
loff_t t;
|
if (de->first || de->last) {
|
hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
|
hpfs_brelse4(qbh);
|
return 1;
|
}
|
if (de->down) down = de_down_pointer(de);
|
if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
|
if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
|
hpfs_brelse4(qbh);
|
return 2;
|
}
|
}
|
for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
|
hpfs_delete_de(i->i_sb, dnode, de);
|
hpfs_mark_4buffers_dirty(qbh);
|
hpfs_brelse4(qbh);
|
if (down) {
|
dnode_secno a = move_to_top(i, down, dno);
|
for_all_poss(i, hpfs_pos_subst, 5, t);
|
if (a) delete_empty_dnode(i, a);
|
return !a;
|
}
|
delete_empty_dnode(i, dno);
|
return 0;
|
}
|
|
void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
|
int *n_subdirs, int *n_items)
|
{
|
struct dnode *dnode;
|
struct quad_buffer_head qbh;
|
struct hpfs_dirent *de;
|
dnode_secno ptr, odno = 0;
|
int c1, c2 = 0;
|
int d1, d2 = 0;
|
go_down:
|
if (n_dnodes) (*n_dnodes)++;
|
if (hpfs_sb(s)->sb_chk)
|
if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
|
ptr = 0;
|
go_up:
|
if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
|
if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && le32_to_cpu(dnode->up) != odno)
|
hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, le32_to_cpu(dnode->up));
|
de = dnode_first_de(dnode);
|
if (ptr) while(1) {
|
if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
|
if (de->last) {
|
hpfs_brelse4(&qbh);
|
hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
|
ptr, dno, odno);
|
return;
|
}
|
de = de_next_de(de);
|
}
|
next_de:
|
if (de->down) {
|
odno = dno;
|
dno = de_down_pointer(de);
|
hpfs_brelse4(&qbh);
|
goto go_down;
|
}
|
process_de:
|
if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
|
if (!de->first && !de->last && n_items) (*n_items)++;
|
if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
|
ptr = dno;
|
dno = le32_to_cpu(dnode->up);
|
if (dnode->root_dnode) {
|
hpfs_brelse4(&qbh);
|
return;
|
}
|
hpfs_brelse4(&qbh);
|
if (hpfs_sb(s)->sb_chk)
|
if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
|
odno = -1;
|
goto go_up;
|
}
|
|
static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
|
struct quad_buffer_head *qbh, struct dnode **dn)
|
{
|
int i;
|
struct hpfs_dirent *de, *de_end;
|
struct dnode *dnode;
|
dnode = hpfs_map_dnode(s, dno, qbh);
|
if (!dnode) return NULL;
|
if (dn) *dn=dnode;
|
de = dnode_first_de(dnode);
|
de_end = dnode_end_de(dnode);
|
for (i = 1; de < de_end; i++, de = de_next_de(de)) {
|
if (i == n) {
|
return de;
|
}
|
if (de->last) break;
|
}
|
hpfs_brelse4(qbh);
|
hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
|
return NULL;
|
}
|
|
dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
|
{
|
struct quad_buffer_head qbh;
|
dnode_secno d = dno;
|
dnode_secno up = 0;
|
struct hpfs_dirent *de;
|
int c1, c2 = 0;
|
|
again:
|
if (hpfs_sb(s)->sb_chk)
|
if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
|
return d;
|
if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
|
if (hpfs_sb(s)->sb_chk)
|
if (up && le32_to_cpu(((struct dnode *)qbh.data)->up) != up)
|
hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, le32_to_cpu(((struct dnode *)qbh.data)->up));
|
if (!de->down) {
|
hpfs_brelse4(&qbh);
|
return d;
|
}
|
up = d;
|
d = de_down_pointer(de);
|
hpfs_brelse4(&qbh);
|
goto again;
|
}
|
|
struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
|
struct quad_buffer_head *qbh)
|
{
|
loff_t pos;
|
unsigned c;
|
dnode_secno dno;
|
struct hpfs_dirent *de, *d;
|
struct hpfs_dirent *up_de;
|
struct hpfs_dirent *end_up_de;
|
struct dnode *dnode;
|
struct dnode *up_dnode;
|
struct quad_buffer_head qbh0;
|
|
pos = *posp;
|
dno = pos >> 6 << 2;
|
pos &= 077;
|
if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
|
goto bail;
|
|
/* Going to the next dirent */
|
if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
|
if (!(++*posp & 077)) {
|
hpfs_error(inode->i_sb,
|
"map_pos_dirent: pos crossed dnode boundary; pos = %08llx",
|
(unsigned long long)*posp);
|
goto bail;
|
}
|
/* We're going down the tree */
|
if (d->down) {
|
*posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
|
}
|
|
return de;
|
}
|
|
/* Going up */
|
if (dnode->root_dnode) goto bail;
|
|
if (!(up_dnode = hpfs_map_dnode(inode->i_sb, le32_to_cpu(dnode->up), &qbh0)))
|
goto bail;
|
|
end_up_de = dnode_end_de(up_dnode);
|
c = 0;
|
for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
|
up_de = de_next_de(up_de)) {
|
if (!(++c & 077)) hpfs_error(inode->i_sb,
|
"map_pos_dirent: pos crossed dnode boundary; dnode = %08x", le32_to_cpu(dnode->up));
|
if (up_de->down && de_down_pointer(up_de) == dno) {
|
*posp = ((loff_t) le32_to_cpu(dnode->up) << 4) + c;
|
hpfs_brelse4(&qbh0);
|
return de;
|
}
|
}
|
|
hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
|
dno, le32_to_cpu(dnode->up));
|
hpfs_brelse4(&qbh0);
|
|
bail:
|
*posp = 12;
|
return de;
|
}
|
|
/* Find a dirent in tree */
|
|
struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno,
|
const unsigned char *name, unsigned len,
|
dnode_secno *dd, struct quad_buffer_head *qbh)
|
{
|
struct dnode *dnode;
|
struct hpfs_dirent *de;
|
struct hpfs_dirent *de_end;
|
int c1, c2 = 0;
|
|
if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
|
again:
|
if (hpfs_sb(inode->i_sb)->sb_chk)
|
if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
|
if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
|
|
de_end = dnode_end_de(dnode);
|
for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
|
int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
|
if (!t) {
|
if (dd) *dd = dno;
|
return de;
|
}
|
if (t < 0) {
|
if (de->down) {
|
dno = de_down_pointer(de);
|
hpfs_brelse4(qbh);
|
goto again;
|
}
|
break;
|
}
|
}
|
hpfs_brelse4(qbh);
|
return NULL;
|
}
|
|
/*
|
* Remove empty directory. In normal cases it is only one dnode with two
|
* entries, but we must handle also such obscure cases when it's a tree
|
* of empty dnodes.
|
*/
|
|
void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
|
{
|
struct quad_buffer_head qbh;
|
struct dnode *dnode;
|
struct hpfs_dirent *de;
|
dnode_secno d1, d2, rdno = dno;
|
while (1) {
|
if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
|
de = dnode_first_de(dnode);
|
if (de->last) {
|
if (de->down) d1 = de_down_pointer(de);
|
else goto error;
|
hpfs_brelse4(&qbh);
|
hpfs_free_dnode(s, dno);
|
dno = d1;
|
} else break;
|
}
|
if (!de->first) goto error;
|
d1 = de->down ? de_down_pointer(de) : 0;
|
de = de_next_de(de);
|
if (!de->last) goto error;
|
d2 = de->down ? de_down_pointer(de) : 0;
|
hpfs_brelse4(&qbh);
|
hpfs_free_dnode(s, dno);
|
do {
|
while (d1) {
|
if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
|
de = dnode_first_de(dnode);
|
if (!de->last) goto error;
|
d1 = de->down ? de_down_pointer(de) : 0;
|
hpfs_brelse4(&qbh);
|
hpfs_free_dnode(s, dno);
|
}
|
d1 = d2;
|
d2 = 0;
|
} while (d1);
|
return;
|
error:
|
hpfs_brelse4(&qbh);
|
hpfs_free_dnode(s, dno);
|
hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
|
}
|
|
/*
|
* Find dirent for specified fnode. Use truncated 15-char name in fnode as
|
* a help for searching.
|
*/
|
|
struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
|
struct fnode *f, struct quad_buffer_head *qbh)
|
{
|
unsigned char *name1;
|
unsigned char *name2;
|
int name1len, name2len;
|
struct dnode *d;
|
dnode_secno dno, downd;
|
struct fnode *upf;
|
struct buffer_head *bh;
|
struct hpfs_dirent *de, *de_end;
|
int c;
|
int c1, c2 = 0;
|
int d1, d2 = 0;
|
name1 = f->name;
|
if (!(name2 = kmalloc(256, GFP_NOFS))) {
|
pr_err("out of memory, can't map dirent\n");
|
return NULL;
|
}
|
if (f->len <= 15)
|
memcpy(name2, name1, name1len = name2len = f->len);
|
else {
|
memcpy(name2, name1, 15);
|
memset(name2 + 15, 0xff, 256 - 15);
|
/*name2[15] = 0xff;*/
|
name1len = 15; name2len = 256;
|
}
|
if (!(upf = hpfs_map_fnode(s, le32_to_cpu(f->up), &bh))) {
|
kfree(name2);
|
return NULL;
|
}
|
if (!fnode_is_dir(upf)) {
|
brelse(bh);
|
hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, le32_to_cpu(f->up));
|
kfree(name2);
|
return NULL;
|
}
|
dno = le32_to_cpu(upf->u.external[0].disk_secno);
|
brelse(bh);
|
go_down:
|
downd = 0;
|
go_up:
|
if (!(d = hpfs_map_dnode(s, dno, qbh))) {
|
kfree(name2);
|
return NULL;
|
}
|
de_end = dnode_end_de(d);
|
de = dnode_first_de(d);
|
if (downd) {
|
while (de < de_end) {
|
if (de->down) if (de_down_pointer(de) == downd) goto f;
|
de = de_next_de(de);
|
}
|
hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
|
hpfs_brelse4(qbh);
|
kfree(name2);
|
return NULL;
|
}
|
next_de:
|
if (le32_to_cpu(de->fnode) == fno) {
|
kfree(name2);
|
return de;
|
}
|
c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
|
if (c < 0 && de->down) {
|
dno = de_down_pointer(de);
|
hpfs_brelse4(qbh);
|
if (hpfs_sb(s)->sb_chk)
|
if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
|
kfree(name2);
|
return NULL;
|
}
|
goto go_down;
|
}
|
f:
|
if (le32_to_cpu(de->fnode) == fno) {
|
kfree(name2);
|
return de;
|
}
|
c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
|
if (c < 0 && !de->last) goto not_found;
|
if ((de = de_next_de(de)) < de_end) goto next_de;
|
if (d->root_dnode) goto not_found;
|
downd = dno;
|
dno = le32_to_cpu(d->up);
|
hpfs_brelse4(qbh);
|
if (hpfs_sb(s)->sb_chk)
|
if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
|
kfree(name2);
|
return NULL;
|
}
|
goto go_up;
|
not_found:
|
hpfs_brelse4(qbh);
|
hpfs_error(s, "dirent for fnode %08x not found", fno);
|
kfree(name2);
|
return NULL;
|
}
|
