1131523Stjr/*- 2131523Stjr * Copyright (c) 2003-2004 Tim J. Robbins. 3131523Stjr * All rights reserved. 4131523Stjr * 5131523Stjr * Redistribution and use in source and binary forms, with or without 6131523Stjr * modification, are permitted provided that the following conditions 7131523Stjr * are met: 8131523Stjr * 1. Redistributions of source code must retain the above copyright 9131523Stjr * notice, this list of conditions and the following disclaimer. 10131523Stjr * 2. Redistributions in binary form must reproduce the above copyright 11131523Stjr * notice, this list of conditions and the following disclaimer in the 12131523Stjr * documentation and/or other materials provided with the distribution. 13131523Stjr * 14131523Stjr * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15131523Stjr * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16131523Stjr * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17131523Stjr * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18131523Stjr * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19131523Stjr * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20131523Stjr * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21131523Stjr * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22131523Stjr * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23131523Stjr * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24131523Stjr * SUCH DAMAGE. 25131523Stjr */ 26131523Stjr/* 27131523Stjr * Compress 64-bit file numbers into temporary, unique 32-bit file numbers. 28131523Stjr * This is needed because the algorithm we use to calculate these numbers 29131523Stjr * generates 64-bit quantities, but struct dirent's d_fileno member and 30131523Stjr * struct vnodeattr's va_fileid member only have space for 32 bits. 31131523Stjr * 32131523Stjr * 32-bit file numbers are generated sequentially, and stored in a 33131523Stjr * red-black tree, indexed on 64-bit file number. The mappings do not 34131523Stjr * persist across reboots (or unmounts); anything that relies on this 35131523Stjr * (e.g. NFS) will not work correctly. This scheme consumes 32 bytes 36131523Stjr * of kernel memory per file (on i386), and it may be possible for a user 37131523Stjr * to cause a panic by creating millions of tiny files. 38131523Stjr * 39131523Stjr * As an optimization, we split the file number space between statically 40131523Stjr * allocated and dynamically allocated. File numbers less than 41131523Stjr * FILENO_FIRST_DYN are left unchanged and do not have any tree nodes 42131523Stjr * allocated to them. 43131523Stjr */ 44131523Stjr 45131523Stjr#include <sys/cdefs.h> 46131523Stjr__FBSDID("$FreeBSD$"); 47131523Stjr 48131523Stjr#include <sys/param.h> 49131523Stjr#include <sys/systm.h> 50131523Stjr#include <sys/kernel.h> 51171750Sbde#include <sys/lock.h> 52171750Sbde#include <sys/malloc.h> 53131523Stjr#include <sys/mount.h> 54131523Stjr 55131523Stjr#include <fs/msdosfs/bpb.h> 56171750Sbde#include <fs/msdosfs/direntry.h> 57131523Stjr#include <fs/msdosfs/msdosfsmount.h> 58131523Stjr 59151897Srwatsonstatic MALLOC_DEFINE(M_MSDOSFSFILENO, "msdosfs_fileno", "MSDOSFS fileno mapping node"); 60131523Stjr 61131523StjrRB_PROTOTYPE(msdosfs_filenotree, msdosfs_fileno, mf_tree, 62131523Stjr msdosfs_fileno_compare) 63131523Stjr 64131523Stjrstatic int msdosfs_fileno_compare(struct msdosfs_fileno *, 65131523Stjr struct msdosfs_fileno *); 66131523Stjr 67131523Stjr#define FILENO_FIRST_DYN 0xf0000000 68131523Stjr 69131523Stjr/* Initialize file number mapping structures. */ 70131523Stjrvoid 71131523Stjrmsdosfs_fileno_init(mp) 72131523Stjr struct mount *mp; 73131523Stjr{ 74131523Stjr struct msdosfsmount *pmp = VFSTOMSDOSFS(mp); 75131523Stjr 76131523Stjr RB_INIT(&pmp->pm_filenos); 77131523Stjr pmp->pm_nfileno = FILENO_FIRST_DYN; 78263670Spfg if (pmp->pm_HugeSectors > 0xffffffff / 79131523Stjr (pmp->pm_BytesPerSec / sizeof(struct direntry)) + 1) 80131523Stjr pmp->pm_flags |= MSDOSFS_LARGEFS; 81131523Stjr} 82131523Stjr 83131523Stjr/* Free 32-bit file number generation structures. */ 84131523Stjrvoid 85131523Stjrmsdosfs_fileno_free(mp) 86131523Stjr struct mount *mp; 87131523Stjr{ 88131523Stjr struct msdosfsmount *pmp = VFSTOMSDOSFS(mp); 89131523Stjr struct msdosfs_fileno *mf, *next; 90131523Stjr 91131523Stjr for (mf = RB_MIN(msdosfs_filenotree, &pmp->pm_filenos); mf != NULL; 92131523Stjr mf = next) { 93131523Stjr next = RB_NEXT(msdosfs_filenotree, &pmp->pm_filenos, mf); 94131523Stjr RB_REMOVE(msdosfs_filenotree, &pmp->pm_filenos, mf); 95131523Stjr free(mf, M_MSDOSFSFILENO); 96131523Stjr } 97131523Stjr} 98131523Stjr 99131523Stjr/* Map a 64-bit file number into a 32-bit one. */ 100131523Stjruint32_t 101131523Stjrmsdosfs_fileno_map(mp, fileno) 102131523Stjr struct mount *mp; 103131523Stjr uint64_t fileno; 104131523Stjr{ 105131523Stjr struct msdosfsmount *pmp = VFSTOMSDOSFS(mp); 106131523Stjr struct msdosfs_fileno key, *mf, *tmf; 107131523Stjr uint32_t mapped; 108131523Stjr 109131523Stjr if ((pmp->pm_flags & MSDOSFS_LARGEFS) == 0) { 110131523Stjr KASSERT((uint32_t)fileno == fileno, 111131523Stjr ("fileno >32 bits but not a large fs?")); 112131523Stjr return ((uint32_t)fileno); 113131523Stjr } 114131523Stjr if (fileno < FILENO_FIRST_DYN) 115131523Stjr return ((uint32_t)fileno); 116204473Skib MSDOSFS_LOCK_MP(pmp); 117131523Stjr key.mf_fileno64 = fileno; 118131523Stjr mf = RB_FIND(msdosfs_filenotree, &pmp->pm_filenos, &key); 119131523Stjr if (mf != NULL) { 120131523Stjr mapped = mf->mf_fileno32; 121204473Skib MSDOSFS_UNLOCK_MP(pmp); 122131523Stjr return (mapped); 123131523Stjr } 124131523Stjr if (pmp->pm_nfileno < FILENO_FIRST_DYN) 125131523Stjr panic("msdosfs_fileno_map: wraparound"); 126204473Skib MSDOSFS_UNLOCK_MP(pmp); 127131523Stjr mf = malloc(sizeof(*mf), M_MSDOSFSFILENO, M_WAITOK); 128204473Skib MSDOSFS_LOCK_MP(pmp); 129131523Stjr tmf = RB_FIND(msdosfs_filenotree, &pmp->pm_filenos, &key); 130131523Stjr if (tmf != NULL) { 131131523Stjr mapped = tmf->mf_fileno32; 132204473Skib MSDOSFS_UNLOCK_MP(pmp); 133131523Stjr free(mf, M_MSDOSFSFILENO); 134131523Stjr return (mapped); 135131523Stjr } 136131523Stjr mf->mf_fileno64 = fileno; 137131523Stjr mapped = mf->mf_fileno32 = pmp->pm_nfileno++; 138131523Stjr RB_INSERT(msdosfs_filenotree, &pmp->pm_filenos, mf); 139204473Skib MSDOSFS_UNLOCK_MP(pmp); 140131523Stjr return (mapped); 141131523Stjr} 142131523Stjr 143131523Stjr/* Compare by 64-bit file number. */ 144131523Stjrstatic int 145131523Stjrmsdosfs_fileno_compare(fa, fb) 146131523Stjr struct msdosfs_fileno *fa, *fb; 147131523Stjr{ 148131523Stjr 149131523Stjr if (fa->mf_fileno64 > fb->mf_fileno64) 150131523Stjr return (1); 151131523Stjr else if (fa->mf_fileno64 < fb->mf_fileno64) 152131523Stjr return (-1); 153131523Stjr return (0); 154131523Stjr} 155131523Stjr 156131523StjrRB_GENERATE(msdosfs_filenotree, msdosfs_fileno, mf_tree, 157131523Stjr msdosfs_fileno_compare) 158