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 71276887Semastemsdosfs_fileno_init(struct mount *mp) 72131523Stjr{ 73131523Stjr struct msdosfsmount *pmp = VFSTOMSDOSFS(mp); 74131523Stjr 75131523Stjr RB_INIT(&pmp->pm_filenos); 76131523Stjr pmp->pm_nfileno = FILENO_FIRST_DYN; 77263441Spfg if (pmp->pm_HugeSectors > 0xffffffff / 78131523Stjr (pmp->pm_BytesPerSec / sizeof(struct direntry)) + 1) 79131523Stjr pmp->pm_flags |= MSDOSFS_LARGEFS; 80131523Stjr} 81131523Stjr 82131523Stjr/* Free 32-bit file number generation structures. */ 83131523Stjrvoid 84276887Semastemsdosfs_fileno_free(struct mount *mp) 85131523Stjr{ 86131523Stjr struct msdosfsmount *pmp = VFSTOMSDOSFS(mp); 87131523Stjr struct msdosfs_fileno *mf, *next; 88131523Stjr 89131523Stjr for (mf = RB_MIN(msdosfs_filenotree, &pmp->pm_filenos); mf != NULL; 90131523Stjr mf = next) { 91131523Stjr next = RB_NEXT(msdosfs_filenotree, &pmp->pm_filenos, mf); 92131523Stjr RB_REMOVE(msdosfs_filenotree, &pmp->pm_filenos, mf); 93131523Stjr free(mf, M_MSDOSFSFILENO); 94131523Stjr } 95131523Stjr} 96131523Stjr 97131523Stjr/* Map a 64-bit file number into a 32-bit one. */ 98131523Stjruint32_t 99276887Semastemsdosfs_fileno_map(struct mount *mp, uint64_t fileno) 100131523Stjr{ 101131523Stjr struct msdosfsmount *pmp = VFSTOMSDOSFS(mp); 102131523Stjr struct msdosfs_fileno key, *mf, *tmf; 103131523Stjr uint32_t mapped; 104131523Stjr 105131523Stjr if ((pmp->pm_flags & MSDOSFS_LARGEFS) == 0) { 106131523Stjr KASSERT((uint32_t)fileno == fileno, 107131523Stjr ("fileno >32 bits but not a large fs?")); 108131523Stjr return ((uint32_t)fileno); 109131523Stjr } 110131523Stjr if (fileno < FILENO_FIRST_DYN) 111131523Stjr return ((uint32_t)fileno); 112204473Skib MSDOSFS_LOCK_MP(pmp); 113131523Stjr key.mf_fileno64 = fileno; 114131523Stjr mf = RB_FIND(msdosfs_filenotree, &pmp->pm_filenos, &key); 115131523Stjr if (mf != NULL) { 116131523Stjr mapped = mf->mf_fileno32; 117204473Skib MSDOSFS_UNLOCK_MP(pmp); 118131523Stjr return (mapped); 119131523Stjr } 120131523Stjr if (pmp->pm_nfileno < FILENO_FIRST_DYN) 121131523Stjr panic("msdosfs_fileno_map: wraparound"); 122204473Skib MSDOSFS_UNLOCK_MP(pmp); 123131523Stjr mf = malloc(sizeof(*mf), M_MSDOSFSFILENO, M_WAITOK); 124204473Skib MSDOSFS_LOCK_MP(pmp); 125131523Stjr tmf = RB_FIND(msdosfs_filenotree, &pmp->pm_filenos, &key); 126131523Stjr if (tmf != NULL) { 127131523Stjr mapped = tmf->mf_fileno32; 128204473Skib MSDOSFS_UNLOCK_MP(pmp); 129131523Stjr free(mf, M_MSDOSFSFILENO); 130131523Stjr return (mapped); 131131523Stjr } 132131523Stjr mf->mf_fileno64 = fileno; 133131523Stjr mapped = mf->mf_fileno32 = pmp->pm_nfileno++; 134131523Stjr RB_INSERT(msdosfs_filenotree, &pmp->pm_filenos, mf); 135204473Skib MSDOSFS_UNLOCK_MP(pmp); 136131523Stjr return (mapped); 137131523Stjr} 138131523Stjr 139131523Stjr/* Compare by 64-bit file number. */ 140131523Stjrstatic int 141276887Semastemsdosfs_fileno_compare(struct msdosfs_fileno *fa, struct msdosfs_fileno *fb) 142131523Stjr{ 143131523Stjr 144131523Stjr if (fa->mf_fileno64 > fb->mf_fileno64) 145131523Stjr return (1); 146131523Stjr else if (fa->mf_fileno64 < fb->mf_fileno64) 147131523Stjr return (-1); 148131523Stjr return (0); 149131523Stjr} 150131523Stjr 151131523StjrRB_GENERATE(msdosfs_filenotree, msdosfs_fileno, mf_tree, 152131523Stjr msdosfs_fileno_compare) 153