cregit-Linux how code gets into the kernel

Release 4.18 fs/hfs/bnode.c

Directory: fs/hfs
// SPDX-License-Identifier: GPL-2.0
/*
 *  linux/fs/hfs/bnode.c
 *
 * Copyright (C) 2001
 * Brad Boyer (flar@allandria.com)
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 *
 * Handle basic btree node operations
 */

#include <linux/pagemap.h>
#include <linux/slab.h>
#include <linux/swap.h>

#include "btree.h"


void hfs_bnode_read(struct hfs_bnode *node, void *buf, int off, int len) { struct page *page; off += node->page_offset; page = node->page[0]; memcpy(buf, kmap(page) + off, len); kunmap(page); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton59100.00%1100.00%
Total59100.00%1100.00%


u16 hfs_bnode_read_u16(struct hfs_bnode *node, int off) { __be16 data; // optimize later... hfs_bnode_read(node, &data, off, 2); return be16_to_cpu(data); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton3497.14%150.00%
Al Viro12.86%150.00%
Total35100.00%2100.00%


u8 hfs_bnode_read_u8(struct hfs_bnode *node, int off) { u8 data; // optimize later... hfs_bnode_read(node, &data, off, 1); return data; }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton32100.00%1100.00%
Total32100.00%1100.00%


void hfs_bnode_read_key(struct hfs_bnode *node, void *key, int off) { struct hfs_btree *tree; int key_len; tree = node->tree; if (node->type == HFS_NODE_LEAF || tree->attributes & HFS_TREE_VARIDXKEYS) key_len = hfs_bnode_read_u8(node, off) + 1; else key_len = tree->max_key_len + 1; hfs_bnode_read(node, key, off, key_len); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton76100.00%1100.00%
Total76100.00%1100.00%


void hfs_bnode_write(struct hfs_bnode *node, void *buf, int off, int len) { struct page *page; off += node->page_offset; page = node->page[0]; memcpy(kmap(page) + off, buf, len); kunmap(page); set_page_dirty(page); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton64100.00%1100.00%
Total64100.00%1100.00%


void hfs_bnode_write_u16(struct hfs_bnode *node, int off, u16 data) { __be16 v = cpu_to_be16(data); // optimize later... hfs_bnode_write(node, &v, off, 2); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton3286.49%150.00%
Al Viro513.51%150.00%
Total37100.00%2100.00%


void hfs_bnode_write_u8(struct hfs_bnode *node, int off, u8 data) { // optimize later... hfs_bnode_write(node, &data, off, 1); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton29100.00%1100.00%
Total29100.00%1100.00%


void hfs_bnode_clear(struct hfs_bnode *node, int off, int len) { struct page *page; off += node->page_offset; page = node->page[0]; memset(kmap(page) + off, 0, len); kunmap(page); set_page_dirty(page); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton60100.00%1100.00%
Total60100.00%1100.00%


void hfs_bnode_copy(struct hfs_bnode *dst_node, int dst, struct hfs_bnode *src_node, int src, int len) { struct page *src_page, *dst_page; hfs_dbg(BNODE_MOD, "copybytes: %u,%u,%u\n", dst, src, len); if (!len) return; src += src_node->page_offset; dst += dst_node->page_offset; src_page = src_node->page[0]; dst_page = dst_node->page[0]; memcpy(kmap(dst_page) + dst, kmap(src_page) + src, len); kunmap(src_page); kunmap(dst_page); set_page_dirty(dst_page); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton11398.26%150.00%
Joe Perches21.74%150.00%
Total115100.00%2100.00%


void hfs_bnode_move(struct hfs_bnode *node, int dst, int src, int len) { struct page *page; void *ptr; hfs_dbg(BNODE_MOD, "movebytes: %u,%u,%u\n", dst, src, len); if (!len) return; src += node->page_offset; dst += node->page_offset; page = node->page[0]; ptr = kmap(page); memmove(ptr + dst, ptr + src, len); kunmap(page); set_page_dirty(page); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton9697.96%150.00%
Joe Perches22.04%150.00%
Total98100.00%2100.00%


void hfs_bnode_dump(struct hfs_bnode *node) { struct hfs_bnode_desc desc; __be32 cnid; int i, off, key_off; hfs_dbg(BNODE_MOD, "bnode: %d\n", node->this); hfs_bnode_read(node, &desc, 0, sizeof(desc)); hfs_dbg(BNODE_MOD, "%d, %d, %d, %d, %d\n", be32_to_cpu(desc.next), be32_to_cpu(desc.prev), desc.type, desc.height, be16_to_cpu(desc.num_recs)); off = node->tree->node_size - 2; for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) { key_off = hfs_bnode_read_u16(node, off); hfs_dbg_cont(BNODE_MOD, " %d", key_off); if (i && node->type == HFS_NODE_INDEX) { int tmp; if (node->tree->attributes & HFS_TREE_VARIDXKEYS) tmp = (hfs_bnode_read_u8(node, key_off) | 1) + 1; else tmp = node->tree->max_key_len + 1; hfs_dbg_cont(BNODE_MOD, " (%d,%d", tmp, hfs_bnode_read_u8(node, key_off)); hfs_bnode_read(node, &cnid, key_off + tmp, 4); hfs_dbg_cont(BNODE_MOD, ",%d)", be32_to_cpu(cnid)); } else if (i && node->type == HFS_NODE_LEAF) { int tmp; tmp = hfs_bnode_read_u8(node, key_off); hfs_dbg_cont(BNODE_MOD, " (%d)", tmp); } } hfs_dbg_cont(BNODE_MOD, "\n"); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton25292.65%125.00%
Joe Perches145.15%125.00%
Linus Torvalds (pre-git)51.84%125.00%
Al Viro10.37%125.00%
Total272100.00%4100.00%


void hfs_bnode_unlink(struct hfs_bnode *node) { struct hfs_btree *tree; struct hfs_bnode *tmp; __be32 cnid; tree = node->tree; if (node->prev) { tmp = hfs_bnode_find(tree, node->prev); if (IS_ERR(tmp)) return; tmp->next = node->next; cnid = cpu_to_be32(tmp->next); hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, next), 4); hfs_bnode_put(tmp); } else if (node->type == HFS_NODE_LEAF) tree->leaf_head = node->next; if (node->next) { tmp = hfs_bnode_find(tree, node->next); if (IS_ERR(tmp)) return; tmp->prev = node->prev; cnid = cpu_to_be32(tmp->prev); hfs_bnode_write(tmp, &cnid, offsetof(struct hfs_bnode_desc, prev), 4); hfs_bnode_put(tmp); } else if (node->type == HFS_NODE_LEAF) tree->leaf_tail = node->prev; // move down? if (!node->prev && !node->next) { printk(KERN_DEBUG "hfs_btree_del_level\n"); } if (!node->parent) { tree->root = 0; tree->depth = 0; } set_bit(HFS_BNODE_DELETED, &node->flags); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton21084.34%125.00%
Linus Torvalds (pre-git)3714.86%125.00%
Al Viro10.40%125.00%
Roman Zippel10.40%125.00%
Total249100.00%4100.00%


static inline int hfs_bnode_hash(u32 num) { num = (num >> 16) + num; num += num >> 8; return num & (NODE_HASH_SIZE - 1); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton3394.29%150.00%
Linus Torvalds (pre-git)25.71%150.00%
Total35100.00%2100.00%


struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid) { struct hfs_bnode *node; if (cnid >= tree->node_count) { pr_err("request for non-existent node %d in B*Tree\n", cnid); return NULL; } for (node = tree->node_hash[hfs_bnode_hash(cnid)]; node; node = node->next_hash) { if (node->this == cnid) { return node; } } return NULL; }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton6378.75%133.33%
Linus Torvalds (pre-git)1518.75%133.33%
Joe Perches22.50%133.33%
Total80100.00%3100.00%


static struct hfs_bnode *__hfs_bnode_create(struct hfs_btree *tree, u32 cnid) { struct hfs_bnode *node, *node2; struct address_space *mapping; struct page *page; int size, block, i, hash; loff_t off; if (cnid >= tree->node_count) { pr_err("request for non-existent node %d in B*Tree\n", cnid); return NULL; } size = sizeof(struct hfs_bnode) + tree->pages_per_bnode * sizeof(struct page *); node = kzalloc(size, GFP_KERNEL); if (!node) return NULL; node->tree = tree; node->this = cnid; set_bit(HFS_BNODE_NEW, &node->flags); atomic_set(&node->refcnt, 1); hfs_dbg(BNODE_REFS, "new_node(%d:%d): 1\n", node->tree->cnid, node->this); init_waitqueue_head(&node->lock_wq); spin_lock(&tree->hash_lock); node2 = hfs_bnode_findhash(tree, cnid); if (!node2) { hash = hfs_bnode_hash(cnid); node->next_hash = tree->node_hash[hash]; tree->node_hash[hash] = node; tree->node_hash_cnt++; } else { spin_unlock(&tree->hash_lock); kfree(node); wait_event(node2->lock_wq, !test_bit(HFS_BNODE_NEW, &node2->flags)); return node2; } spin_unlock(&tree->hash_lock); mapping = tree->inode->i_mapping; off = (loff_t)cnid * tree->node_size; block = off >> PAGE_SHIFT; node->page_offset = off & ~PAGE_MASK; for (i = 0; i < tree->pages_per_bnode; i++) { page = read_mapping_page(mapping, block++, NULL); if (IS_ERR(page)) goto fail; if (PageError(page)) { put_page(page); goto fail; } node->page[i] = page; } return node; fail: set_bit(HFS_BNODE_ERROR, &node->flags); return node; }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton23061.01%111.11%
Linus Torvalds (pre-git)12232.36%222.22%
Roman Zippel164.24%111.11%
Joe Perches41.06%222.22%
Kirill A. Shutemov30.80%111.11%
Panagiotis Issaris10.27%111.11%
Pekka J Enberg10.27%111.11%
Total377100.00%9100.00%


void hfs_bnode_unhash(struct hfs_bnode *node) { struct hfs_bnode **p; hfs_dbg(BNODE_REFS, "remove_node(%d:%d): %d\n", node->tree->cnid, node->this, atomic_read(&node->refcnt)); for (p = &node->tree->node_hash[hfs_bnode_hash(node->this)]; *p && *p != node; p = &(*p)->next_hash) ; BUG_ON(!*p); *p = node->next_hash; node->tree->node_hash_cnt--; }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton8585.00%125.00%
Linus Torvalds (pre-git)1010.00%125.00%
Eric Sesterhenn / Snakebyte33.00%125.00%
Joe Perches22.00%125.00%
Total100100.00%4100.00%

/* Load a particular node out of a tree */
struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) { struct hfs_bnode *node; struct hfs_bnode_desc *desc; int i, rec_off, off, next_off; int entry_size, key_size; spin_lock(&tree->hash_lock); node = hfs_bnode_findhash(tree, num); if (node) { hfs_bnode_get(node); spin_unlock(&tree->hash_lock); wait_event(node->lock_wq, !test_bit(HFS_BNODE_NEW, &node->flags)); if (test_bit(HFS_BNODE_ERROR, &node->flags)) goto node_error; return node; } spin_unlock(&tree->hash_lock); node = __hfs_bnode_create(tree, num); if (!node) return ERR_PTR(-ENOMEM); if (test_bit(HFS_BNODE_ERROR, &node->flags)) goto node_error; if (!test_bit(HFS_BNODE_NEW, &node->flags)) return node; desc = (struct hfs_bnode_desc *)(kmap(node->page[0]) + node->page_offset); node->prev = be32_to_cpu(desc->prev); node->next = be32_to_cpu(desc->next); node->num_recs = be16_to_cpu(desc->num_recs); node->type = desc->type; node->height = desc->height; kunmap(node->page[0]); switch (node->type) { case HFS_NODE_HEADER: case HFS_NODE_MAP: if (node->height != 0) goto node_error; break; case HFS_NODE_LEAF: if (node->height != 1) goto node_error; break; case HFS_NODE_INDEX: if (node->height <= 1 || node->height > tree->depth) goto node_error; break; default: goto node_error; } rec_off = tree->node_size - 2; off = hfs_bnode_read_u16(node, rec_off); if (off != sizeof(struct hfs_bnode_desc)) goto node_error; for (i = 1; i <= node->num_recs; off = next_off, i++) { rec_off -= 2; next_off = hfs_bnode_read_u16(node, rec_off); if (next_off <= off || next_off > tree->node_size || next_off & 1) goto node_error; entry_size = next_off - off; if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF) continue; key_size = hfs_bnode_read_u8(node, off) + 1; if (key_size >= entry_size /*|| key_size & 1*/) goto node_error; } clear_bit(HFS_BNODE_NEW, &node->flags); wake_up(&node->lock_wq); return node; node_error: set_bit(HFS_BNODE_ERROR, &node->flags); clear_bit(HFS_BNODE_NEW, &node->flags); wake_up(&node->lock_wq); hfs_bnode_put(node); return ERR_PTR(-EIO); }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton35770.14%125.00%
Linus Torvalds (pre-git)12223.97%250.00%
Roman Zippel305.89%125.00%
Total509100.00%4100.00%


void hfs_bnode_free(struct hfs_bnode *node) { int i; for (i = 0; i < node->tree->pages_per_bnode; i++) if (node->page[i]) put_page(node->page[i]); kfree(node); }

Contributors

PersonTokensPropCommitsCommitProp
Hin-Tak Leung3870.37%133.33%
Andrew Morton1527.78%133.33%
Kirill A. Shutemov11.85%133.33%
Total54100.00%3100.00%


struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num) { struct hfs_bnode *node; struct page **pagep; int i; spin_lock(&tree->hash_lock); node = hfs_bnode_findhash(tree, num); spin_unlock(&tree->hash_lock); if (node) { pr_crit("new node %u already hashed?\n", num); WARN_ON(1); return node; } node = __hfs_bnode_create(tree, num); if (!node) return ERR_PTR(-ENOMEM); if (test_bit(HFS_BNODE_ERROR, &node->flags)) { hfs_bnode_put(node); return ERR_PTR(-EIO); } pagep = node->page; memset(kmap(*pagep) + node->page_offset, 0, min((int)PAGE_SIZE, (int)tree->node_size)); set_page_dirty(*pagep); kunmap(*pagep); for (i = 1; i < tree->pages_per_bnode; i++) { memset(kmap(*++pagep), 0, PAGE_SIZE); set_page_dirty(*pagep); kunmap(*pagep); } clear_bit(HFS_BNODE_NEW, &node->flags); wake_up(&node->lock_wq); return node; }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton11649.57%116.67%
Linus Torvalds (pre-git)7130.34%116.67%
Roman Zippel2611.11%116.67%
Jeff Mahoney187.69%116.67%
Kirill A. Shutemov20.85%116.67%
Eric Sesterhenn / Snakebyte10.43%116.67%
Total234100.00%6100.00%


void hfs_bnode_get(struct hfs_bnode *node) { if (node) { atomic_inc(&node->refcnt); hfs_dbg(BNODE_REFS, "get_node(%d:%d): %d\n", node->tree->cnid, node->this, atomic_read(&node->refcnt)); } }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton2755.10%125.00%
Linus Torvalds (pre-git)2040.82%250.00%
Joe Perches24.08%125.00%
Total49100.00%4100.00%

/* Dispose of resources used by a node */
void hfs_bnode_put(struct hfs_bnode *node) { if (node) { struct hfs_btree *tree = node->tree; int i; hfs_dbg(BNODE_REFS, "put_node(%d:%d): %d\n", node->tree->cnid, node->this, atomic_read(&node->refcnt)); BUG_ON(!atomic_read(&node->refcnt)); if (!atomic_dec_and_lock(&node->refcnt, &tree->hash_lock)) return; for (i = 0; i < tree->pages_per_bnode; i++) { if (!node->page[i]) continue; mark_page_accessed(node->page[i]); } if (test_bit(HFS_BNODE_DELETED, &node->flags)) { hfs_bnode_unhash(node); spin_unlock(&tree->hash_lock); hfs_bmap_free(node); hfs_bnode_free(node); return; } spin_unlock(&tree->hash_lock); } }

Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton10563.25%120.00%
Linus Torvalds (pre-git)4527.11%120.00%
Roman Zippel116.63%120.00%
Eric Sesterhenn / Snakebyte31.81%120.00%
Joe Perches21.20%120.00%
Total166100.00%5100.00%


Overall Contributors

PersonTokensPropCommitsCommitProp
Andrew Morton209876.40%15.26%
Linus Torvalds (pre-git)45116.42%421.05%
Roman Zippel843.06%315.79%
Hin-Tak Leung381.38%15.26%
Joe Perches301.09%210.53%
Jeff Mahoney180.66%15.26%
Al Viro80.29%15.26%
Eric Sesterhenn / Snakebyte70.25%15.26%
Kirill A. Shutemov60.22%15.26%
Tejun Heo30.11%15.26%
Pekka J Enberg10.04%15.26%
Panagiotis Issaris10.04%15.26%
Greg Kroah-Hartman10.04%15.26%
Total2746100.00%19100.00%
Directory: fs/hfs
Information contained on this website is for historical information purposes only and does not indicate or represent copyright ownership.
Created with cregit.