Kernel Bug-Vulnerability-Comment library - Chinaunix

linux-2.6.17.x/drivers/net/ppp_generic.c
static void cardmap_set(struct cardmap **pmap, unsigned int nr, void *ptr)
{
struct cardmap *p;
int i;
p = *pmap;
if (p == NULL || (nr >> p->shift) >= CARDMAP_WIDTH) {
do {
/* need a new top level */
struct cardmap *np = kmalloc(sizeof(*np), GFP_KERNEL);
/*
* ￥6
* if (np == NULL)
* what_to_do???
*/
memset(np, 0, sizeof(*np));
np->ptr[0] = p;
if (p != NULL) {
np->shift = p->shift + CARDMAP_ORDER;
p->parent = np;
} else
np->shift = 0;
p = np;
/*
* ￥3
* if (p->shift == 0)
* ask_linuz_stop_while_loop???
*/
} while ((nr >> p->shift) >= CARDMAP_WIDTH);
*pmap = p;
}
while (p->shift > 0) {
i = (nr >> p->shift) & CARDMAP_MASK;
if (p->ptr[i] == NULL) {
struct cardmap *np = kmalloc(sizeof(*np), GFP_KERNEL);
memset(np, 0, sizeof(*np));
np->shift = p->shift - CARDMAP_ORDER;
np->parent = p;
p->ptr[i] = np;
}
if (ptr == NULL)
clear_bit(i, &p->inuse);
p = p->ptr[i];
}
i = nr & CARDMAP_MASK;
p->ptr[i] = ptr;
if (ptr != NULL)
set_bit(i, &p->inuse);
else
clear_bit(i, &p->inuse);
}

复制代码

linux-2.6.22.1/kernel/time/timer_list.c
static void print_active_timers(struct seq_file *m,
struct hrtimer_clock_base *base, u64 now)
{
struct hrtimer *timer, tmp;
unsigned long next = 0, i;
struct rb_node *curr;
unsigned long flags;
next_one:
i = 0;
spin_lock_irqsave(&base->cpu_base->lock, flags);
curr = base->first;
/*
* Crude but we have to do this O(N*N) thing, because
* we have to unlock the base when printing:
*/
while (curr && i < next) {
curr = rb_next(curr);
i++;
}
if (curr) {
timer = rb_entry(curr, struct hrtimer, node);
tmp = *timer;
spin_unlock_irqrestore(&base->cpu_base->lock, flags);
/*
* yeah Ingo Molnar, ifuleu,
* but print shows not timer but tmp,
* how can i see %p timer??
*/
print_timer(m, &tmp, i, now);
next++;
goto next_one;
}
spin_unlock_irqrestore(&base->cpu_base->lock, flags);
}

复制代码

/*
* linux-2.6.22.1/net/ipv4/ip_fragment.c
*
* Oops, a fragment queue timed out.
* Kill it and send an ICMP reply.
*
* sisi 2007-8-13 02:27pm
*/
static void ip_expire(unsigned long arg)
{
struct ipq *qp = (struct ipq *) arg;
spin_lock(&qp->lock);
if (qp->last_in & COMPLETE)
goto out;
ipq_kill(qp);
IP_INC_STATS_BH(IPSTATS_MIB_REASMTIMEOUT);
IP_INC_STATS_BH(IPSTATS_MIB_REASMFAILS);
if ((qp->last_in&FIRST_IN) && qp->fragments != NULL) {
struct sk_buff *head = qp->fragments;
/*
* Send an ICMP "Fragment Reassembly Timeout" message.
*
* 由这里引发
*/
if ((head->dev = dev_get_by_index(qp->iif)) != NULL) {
icmp_send(head, ICMP_TIME_EXCEEDED, ICMP_EXC_FRAGTIME, 0);
dev_put(head->dev);
}
}
out:
spin_unlock(&qp->lock);
ipq_put(qp, NULL);
}
void icmp_send(struct sk_buff *skb_in, int type, int code, __be32 info)
{
struct iphdr *iph;
int room;
struct icmp_bxm icmp_param;
struct rtable *rt = (struct rtable *)skb_in->dst;
struct ipcm_cookie ipc;
__be32 saddr;
u8 tos;
if (!rt) {
/* 在这里兑现，
*
* defarg, if issued by netfilter,
* at PRE_ROUTING in normal cases,
* 谁给skb_in->dst赋值？
*
* 本应发送Fragment Reassembly Timeout message，
* 确没有发。
*/
goto out;
}
}

复制代码

shot bug by daemeon
--- linux-2.6.22/net/ipv4/icmp.c 2007-07-09 07:32:17.000000000 +0800
+++ new/net/ipv4/icmp.c 2007-08-13 17:36:21.000000000 +0800
@@ -440,9 +440,6 @@ void icmp_send(struct sk_buff *skb_in, i
__be32 saddr;
u8 tos;
- if (!rt)
- goto out;
-
/*
* Find the original header. It is expected to be valid, of course.
* Check this, icmp_send is called from the most obscure devices
@@ -461,16 +458,24 @@ void icmp_send(struct sk_buff *skb_in, i
goto out;
/*
- * Now check at the protocol level
+ * Only reply to fragment 0. We byte re-order the constant
+ * mask for efficiency.
*/
- if (rt->rt_flags & (RTCF_BROADCAST | RTCF_MULTICAST))
+ if (iph->frag_off & htons(IP_OFFSET))
goto out;
+ if (!rt) {
+ if (ip_route_input(skb_in, iph->daddr, iph->saddr,
+ iph->tos, skb_in->dev) != 0)
+ goto out;
+
+ rt = (struct rtable *)skb_in->dst;
+ }
+
/*
- * Only reply to fragment 0. We byte re-order the constant
- * mask for efficiency.
+ * Now check at the protocol level
*/
- if (iph->frag_off & htons(IP_OFFSET))
+ if (rt->rt_flags & (RTCF_BROADCAST | RTCF_MULTICAST))
goto out;
/*

复制代码

refined by rtable
+ if (!rt) {
+ struct net_device __ndev;
+
+ if (skb_in->input_dev)
+ __ndev = skb_in->input_dev;
+ else
+ __ndev = get_dev_by_index(skb_in->iif);
+ if (!__ndev)
+ goto out;
+
+ if (ip_route_input(skb_in, iph->daddr, iph->saddr,
+ iph->tos, __ndev) != 0)
+ goto out;
+
+ rt = (struct rtable *)skb_in->dst;
+ }

复制代码

/*
* linux-2.6.22.1/net/xfrm/xfrm_state.c
* sisi 2007-8-14 10:44am
*/
int km_report (u8 proto, struct xfrm_selector *sel, xfrm_address_t *addr)
{
int err = -EINVAL;
int ret;
struct xfrm_mgr *km;
read_lock(&xfrm_km_lock);
list_for_each_entry(km, &xfrm_km_list, list) {
if (km->report) {
ret = km->report(proto, sel, addr);
if (!ret)
err = ret;
}
}
read_unlock(&xfrm_km_lock);
/*
* err report bug
*/
return err;
}

复制代码

linux-2.6.20.7 漏洞
static int wanpipe_rcv(struct sk_buff *skb, struct net_device *dev,
struct sock *sk)
{
struct wan_sockaddr_ll * sll = (struct wan_sockaddr_ll *)skb->cb;
wanpipe_common_t * chan = dev->priv;
/*
* When we registered the protocol,
* we saved the socket in the data field for just this event.
*/
skb->dev = dev;
sll->sll_family = AF_WANPIPE;
sll->sll_hatype = dev->type;
sll->sll_protocol = skb->protocol;
sll->sll_pkttype = skb->pkt_type;
sll->sll_ifindex = dev->ifindex;
sll->sll_halen = 0;
if (dev->hard_header_parse)
sll->sll_halen = dev->hard_header_parse(skb, sll->sll_addr);
/*
* WAN_PACKET_DATA : Data which should be passed up the receive queue.
* WAN_PACKET_ASYC : Asynchronous data like place call, which should
* be passed up the listening sock.
* WAN_PACKET_ERR : Asynchronous data like clear call or restart
* which should go into an error queue.
*/
switch (skb->pkt_type) {
case WAN_PACKET_DATA:
if (sock_queue_rcv_skb(sk, skb) < 0) {
return -ENOMEM;
}
break;
case WAN_PACKET_CMD:
sk->sk_state = chan->state;
/* Bug fix: update Mar6.
* Do not set the sock lcn number here, since
* cmd is not guaranteed to be executed on the
* board, thus Lcn could be wrong
*/
sk->sk_data_ready(sk, skb->len);
kfree_skb(skb);
break;
case WAN_PACKET_ERR:
sk->sk_state = chan->state;
if (sock_queue_err_skb(sk,skb)<0){
return -ENOMEM;
}
break;
default:
//at this case 就在这儿，呵呵
printk(KERN_INFO "wansock: BH Illegal Packet Type Dropping\n");
kfree_skb(skb);
break;
}
return 0;
}

复制代码

/*
* linux-2.6.20.7/kernel/time/clocksource.c
*/
static ssize_t sysfs_show_available_clocksources(struct sys_device *dev, char *buf)
{
struct list_head *tmp;
char *curr = buf;
spin_lock_irq(&clocksource_lock);
list_for_each(tmp, &clocksource_list) {
struct clocksource *src;
src = list_entry(tmp, struct clocksource, list);
/*
* no check of buf overflow
*/
curr += sprintf(curr, "%s ", src->name);
}
spin_unlock_irq(&clocksource_lock);
curr += sprintf(curr, "\n");
return curr - buf;
}

复制代码

/*
* linux-2.6.20.7/kernel/time/clocksource.c
*/
static int __init init_clocksource_sysfs(void)
{
int error = sysdev_class_register(&clocksource_sysclass);
if (!error)
error = sysdev_register(&device_clocksource);
if (!error)
error = sysdev_create_file(
&device_clocksource,
&attr_current_clocksource);
/*
* lack of xxx_unregister to clean trash
*/
if (!error)
error = sysdev_create_file(
&device_clocksource,
&attr_available_clocksource);
return error;
}

复制代码

/*
* linux-2.6.20.7/net/ipv4/netfilter/ip_conntrack_core.c
*/
int __init ip_conntrack_init(void)
{
unsigned int i;
int ret;
/* Idea from tcp.c: use 1/16384 of memory. On i386: 32MB
* machine has 256 buckets. >= 1GB machines have 8192 buckets. */
if (!ip_conntrack_htable_size) {
ip_conntrack_htable_size
= (((num_physpages << PAGE_SHIFT) / 16384)
/ sizeof(struct list_head));
if (num_physpages > (1024 * 1024 * 1024 / PAGE_SIZE))
ip_conntrack_htable_size = 8192;
if (ip_conntrack_htable_size < 16)
ip_conntrack_htable_size = 16;
}
ip_conntrack_max = 8 * ip_conntrack_htable_size;
printk("ip_conntrack version %s (%u buckets, %d max)"
" - %Zd bytes per conntrack\n", IP_CONNTRACK_VERSION,
ip_conntrack_htable_size, ip_conntrack_max,
sizeof(struct ip_conntrack));
ret = nf_register_sockopt(&so_getorigdst);
if (ret != 0) {
printk(KERN_ERR "Unable to register netfilter socket option\n");
return ret;
}
ip_conntrack_hash = alloc_hashtable(ip_conntrack_htable_size,
&ip_conntrack_vmalloc);
if (!ip_conntrack_hash) {
printk(KERN_ERR "Unable to create ip_conntrack_hash\n");
goto err_unreg_sockopt;
}
ip_conntrack_cachep = kmem_cache_create("ip_conntrack",
sizeof(struct ip_conntrack), 0,
0, NULL, NULL);
if (!ip_conntrack_cachep) {
printk(KERN_ERR "Unable to create ip_conntrack slab cache\n");
goto err_free_hash;
}
ip_conntrack_expect_cachep = kmem_cache_create("ip_conntrack_expect",
sizeof(struct ip_conntrack_expect),
0, 0, NULL, NULL);
if (!ip_conntrack_expect_cachep) {
printk(KERN_ERR "Unable to create ip_expect slab cache\n");
goto err_free_conntrack_slab;
}
/* Don't NEED lock here, but good form anyway. */
write_lock_bh(&ip_conntrack_lock);
for (i = 0; i < MAX_IP_CT_PROTO; i++)
/*
* potential base upon which issue
* iph->protocol += 32 attack
*/
ip_ct_protos[i] = &ip_conntrack_generic_protocol;
/* Sew in builtin protocols. */
ip_ct_protos[IPPROTO_TCP] = &ip_conntrack_protocol_tcp;
ip_ct_protos[IPPROTO_UDP] = &ip_conntrack_protocol_udp;
ip_ct_protos[IPPROTO_ICMP] = &ip_conntrack_protocol_icmp;
write_unlock_bh(&ip_conntrack_lock);
/* For use by ipt_REJECT */
ip_ct_attach = ip_conntrack_attach;
/* Set up fake conntrack:
- to never be deleted, not in any hashes */
atomic_set(&ip_conntrack_untracked.ct_general.use, 1);
/* - and look it like as a confirmed connection */
set_bit(IPS_CONFIRMED_BIT, &ip_conntrack_untracked.status);
return ret;
err_free_conntrack_slab:
kmem_cache_destroy(ip_conntrack_cachep);
err_free_hash:
free_conntrack_hash(ip_conntrack_hash, ip_conntrack_vmalloc,
ip_conntrack_htable_size);
err_unreg_sockopt:
nf_unregister_sockopt(&so_getorigdst);
return -ENOMEM;
}

复制代码

/*
* linux-2.6.20.7/net/ipv4/netfilter/ip_conntrack_core.c
*
* On success, returns conntrack ptr, sets skb->nfct and ctinfo
*/
static inline struct ip_conntrack *
resolve_normal_ct(struct sk_buff *skb,
struct ip_conntrack_protocol *proto,
int *set_reply,
unsigned int hooknum,
enum ip_conntrack_info *ctinfo)
{
struct ip_conntrack_tuple tuple;
struct ip_conntrack_tuple_hash *h;
struct ip_conntrack *ct;
IP_NF_ASSERT((skb->nh.iph->frag_off & htons(IP_OFFSET)) == 0);
if (!ip_ct_get_tuple(skb->nh.iph, skb, skb->nh.iph->ihl*4,
&tuple,proto))
return NULL;
/* look for tuple match */
h = ip_conntrack_find_get(&tuple, NULL);
if (!h) {
/*
* potential base upon which issue
* pure tcp ack attack
*/
h = init_conntrack(&tuple, proto, skb);
if (!h)
return NULL;
if (IS_ERR(h))
return (void *)h;
}
ct = tuplehash_to_ctrack(h);
/* It exists; we have (non-exclusive) reference. */
if (DIRECTION(h) == IP_CT_DIR_REPLY) {
*ctinfo = IP_CT_ESTABLISHED + IP_CT_IS_REPLY;
/* Please set reply bit if this packet OK */
*set_reply = 1;
} else {
/* Once we've had two way comms, always ESTABLISHED. */
if (test_bit(IPS_SEEN_REPLY_BIT, &ct->status)) {
DEBUGP("ip_conntrack_in: normal packet for %p\n",
ct);
*ctinfo = IP_CT_ESTABLISHED;
} else if (test_bit(IPS_EXPECTED_BIT, &ct->status)) {
DEBUGP("ip_conntrack_in: related packet for %p\n",
ct);
*ctinfo = IP_CT_RELATED;
} else {
DEBUGP("ip_conntrack_in: new packet for %p\n",
ct);
*ctinfo = IP_CT_NEW;
}
*set_reply = 0;
}
skb->nfct = &ct->ct_general;
skb->nfctinfo = *ctinfo;
return ct;
}

复制代码

/*
* linux-2.6.20.7/net/ipv4/netfilter/ip_conntrack_proto_tcp.c
*/
static int tcp_in_window(struct ip_ct_tcp *state,
enum ip_conntrack_dir dir,
unsigned int index,
const struct sk_buff *skb,
struct iphdr *iph,
struct tcphdr *tcph)
{
struct ip_ct_tcp_state *sender = &state->seen[dir];
struct ip_ct_tcp_state *receiver = &state->seen[!dir];
__u32 seq, ack, sack, end, win, swin;
int res;
/*
* Get the required data from the packet.
*/
seq = ntohl(tcph->seq);
ack = sack = ntohl(tcph->ack_seq);
win = ntohs(tcph->window);
end = segment_seq_plus_len(seq, skb->len, iph, tcph);
if (receiver->flags & IP_CT_TCP_FLAG_SACK_PERM)
tcp_sack(skb, iph, tcph, &sack);
DEBUGP("tcp_in_window: START\n");
DEBUGP("tcp_in_window: src=%u.%u.%u.%u:%hu dst=%u.%u.%u.%u:%hu "
"seq=%u ack=%u sack=%u win=%u end=%u\n",
NIPQUAD(iph->saddr), ntohs(tcph->source),
NIPQUAD(iph->daddr), ntohs(tcph->dest),
seq, ack, sack, win, end);
DEBUGP("tcp_in_window: sender end=%u maxend=%u maxwin=%u scale=%i "
"receiver end=%u maxend=%u maxwin=%u scale=%i\n",
sender->td_end, sender->td_maxend, sender->td_maxwin,
sender->td_scale,
receiver->td_end, receiver->td_maxend, receiver->td_maxwin,
receiver->td_scale);
if (sender->td_end == 0) {
/*
* Initialize sender data.
*/
if (tcph->syn && tcph->ack) {
/*
* Outgoing SYN-ACK in reply to a SYN.
*/
sender->td_end =
sender->td_maxend = end;
sender->td_maxwin = (win == 0 ? 1 : win);
tcp_options(skb, iph, tcph, sender);
/*
* RFC 1323:
* Both sides must send the Window Scale option
* to enable window scaling in either direction.
*/
if (!(sender->flags & IP_CT_TCP_FLAG_WINDOW_SCALE
&& receiver->flags & IP_CT_TCP_FLAG_WINDOW_SCALE))
sender->td_scale =
receiver->td_scale = 0;
} else {
/*
* We are in the middle of a connection,
* its history is lost for us.
* Let's try to use the data from the packet.
*/
/*
* why not drop/reject pure tcp ack????
*/
sender->td_end = end;
sender->td_maxwin = (win == 0 ? 1 : win);
sender->td_maxend = end + sender->td_maxwin;
}
} else if (((state->state == TCP_CONNTRACK_SYN_SENT
&& dir == IP_CT_DIR_ORIGINAL)
|| (state->state == TCP_CONNTRACK_SYN_RECV
&& dir == IP_CT_DIR_REPLY))
&& after(end, sender->td_end)) {
/*
* RFC 793: "if a TCP is reinitialized ... then it need
* not wait at all; it must only be sure to use sequence
* numbers larger than those recently used."
*/
sender->td_end =
sender->td_maxend = end;
sender->td_maxwin = (win == 0 ? 1 : win);
tcp_options(skb, iph, tcph, sender);
}
if (!(tcph->ack)) {
/*
* If there is no ACK, just pretend it was set and OK.
*/
ack = sack = receiver->td_end;
} else if (((tcp_flag_word(tcph) & (TCP_FLAG_ACK|TCP_FLAG_RST)) ==
(TCP_FLAG_ACK|TCP_FLAG_RST))
&& (ack == 0)) {
/*
* Broken TCP stacks, that set ACK in RST packets as well
* with zero ack value.
*/
ack = sack = receiver->td_end;
}
if (seq == end
&& (!tcph->rst
|| (seq == 0 && state->state == TCP_CONNTRACK_SYN_SENT)))
/*
* Packets contains no data: we assume it is valid
* and check the ack value only.
* However RST segments are always validated by their
* SEQ number, except when seq == 0 (reset sent answering
* SYN.
*/
seq = end = sender->td_end;
DEBUGP("tcp_in_window: src=%u.%u.%u.%u:%hu dst=%u.%u.%u.%u:%hu "
"seq=%u ack=%u sack =%u win=%u end=%u\n",
NIPQUAD(iph->saddr), ntohs(tcph->source),
NIPQUAD(iph->daddr), ntohs(tcph->dest),
seq, ack, sack, win, end);
DEBUGP("tcp_in_window: sender end=%u maxend=%u maxwin=%u scale=%i "
"receiver end=%u maxend=%u maxwin=%u scale=%i\n",
sender->td_end, sender->td_maxend, sender->td_maxwin,
sender->td_scale,
receiver->td_end, receiver->td_maxend, receiver->td_maxwin,
receiver->td_scale);
DEBUGP("tcp_in_window: I=%i II=%i III=%i IV=%i\n",
before(seq, sender->td_maxend + 1),
after(end, sender->td_end - receiver->td_maxwin - 1),
before(sack, receiver->td_end + 1),
after(ack, receiver->td_end - MAXACKWINDOW(sender)));
if (sender->loose || receiver->loose ||
(before(seq, sender->td_maxend + 1) &&
after(end, sender->td_end - receiver->td_maxwin - 1) &&
before(sack, receiver->td_end + 1) &&
after(ack, receiver->td_end - MAXACKWINDOW(sender)))) {
/*
* Take into account window scaling (RFC 1323).
*/
if (!tcph->syn)
win <<= sender->td_scale;
/*
* Update sender data.
*/
swin = win + (sack - ack);
if (sender->td_maxwin < swin)
sender->td_maxwin = swin;
if (after(end, sender->td_end))
sender->td_end = end;
/*
* Update receiver data.
*/
if (after(end, sender->td_maxend))
receiver->td_maxwin += end - sender->td_maxend;
if (after(sack + win, receiver->td_maxend - 1)) {
receiver->td_maxend = sack + win;
if (win == 0)
receiver->td_maxend++;
}
/*
* Check retransmissions.
*/
if (index == TCP_ACK_SET) {
if (state->last_dir == dir
&& state->last_seq == seq
&& state->last_ack == ack
&& state->last_end == end
&& state->last_win == win)
state->retrans++;
else {
state->last_dir = dir;
state->last_seq = seq;
state->last_ack = ack;
state->last_end = end;
state->last_win = win;
state->retrans = 0;
}
}
/*
* Close the window of disabled window tracking :-)
*/
if (sender->loose)
sender->loose--;
res = 1;
} else {
if (LOG_INVALID(IPPROTO_TCP))
nf_log_packet(PF_INET, 0, skb, NULL, NULL, NULL,
"ip_ct_tcp: %s ",
before(seq, sender->td_maxend + 1) ?
after(end, sender->td_end - receiver->td_maxwin - 1) ?
before(sack, receiver->td_end + 1) ?
after(ack, receiver->td_end - MAXACKWINDOW(sender)) ? "BUG"
: "ACK is under the lower bound (possible overly delayed ACK)"
: "ACK is over the upper bound (ACKed data not seen yet)"
: "SEQ is under the lower bound (already ACKed data retransmitted)"
: "SEQ is over the upper bound (over the window of the receiver)");
res = ip_ct_tcp_be_liberal;
}
DEBUGP("tcp_in_window: res=%i sender end=%u maxend=%u maxwin=%u "
"receiver end=%u maxend=%u maxwin=%u\n",
res, sender->td_end, sender->td_maxend, sender->td_maxwin,
receiver->td_end, receiver->td_maxend, receiver->td_maxwin);
return res;
}

复制代码

/* linux-2.6.20.7/kernel/hrtimer.c
*
* Switch the timer base to the current CPU when possible
*/
static inline struct hrtimer_base *
switch_hrtimer_base(struct hrtimer *timer, struct hrtimer_base *base)
{
struct hrtimer_base *new_base;
new_base = &__get_cpu_var(hrtimer_bases)[base->index];
if (base != new_base) {
/*
* We are trying to schedule the timer on the local CPU.
*
* However we can't change timer's base while it is running,
* so we keep it on the same CPU.
*
* No hassle vs. reprogramming
* the event source in the high resolution case.
*
* The softirq code will take care of this,
* when the timer function has completed.
*
* There is no conflict, as we hold the lock until
* the timer is enqueued.
*/
if (unlikely(base->curr_timer == timer))
return base;
/* See the comment in lock_timer_base() */
timer->base = NULL;
spin_unlock(&base->lock);
/*
* When the timer's base is locked,
* and the timer removed from list,
* it is possible to set timer->base = NULL and
* drop the lock: the timer remains locked.
* =================================
* ￥3
* but during get new_base->lock,
* how about base->curr_timer == timer ???
* any warrant ??? what consequence ???
*/
spin_lock(&new_base->lock);
timer->base = new_base;
}
return new_base;
}

复制代码

/*
* linux-2.6.20.7/kernel/hrtimer.c
*
* Expire the per base hrtimer-queue:
*/
static inline void run_hrtimer_queue(struct hrtimer_base *base)
{
struct rb_node *node;
if (!base->first)
return;
if (base->get_softirq_time)
base->softirq_time = base->get_softirq_time();
spin_lock_irq(&base->lock);
while ((node = base->first)) {
struct hrtimer *timer;
int (*fn)(struct hrtimer *);
int restart;
timer = rb_entry(node, struct hrtimer, node);
if (base->softirq_time.tv64 <= timer->expires.tv64)
break;
fn = timer->function;
set_curr_timer(base, timer);
__remove_hrtimer(timer, base);
spin_unlock_irq(&base->lock);
restart = fn(timer);
spin_lock_irq(&base->lock);
if (restart != HRTIMER_NORESTART) {
BUG_ON(hrtimer_active(timer));
/*
* ￥2
* no check to assure
* 1, fair play among timers
* 2, cpu potentially suck by one timer
*/
enqueue_hrtimer(timer, base);
}
}
set_curr_timer(base, NULL);
spin_unlock_irq(&base->lock);
}

复制代码

/*
* linux-2.6.20.7/net/ipv4/netfilter/ip_conntrack_core.c
* ￥8
* this is not bug/vulnerability in any definition
* but the so-called SBL, single/super big lock,
* as the result of # grep ip_conntrack_lock linux-2.6.20.7/net/ipv4/netfilter/*.c
* show its heavy impact upon performance of netfilter,
* if ip conntrack in running system.
*
* though rcu plays not nice game without lock,
* netfilter shouldnt be only protected by SBL.
*/
DEFINE_RWLOCK(ip_conntrack_lock);

复制代码

static int e1000_clean(struct net_device *poll_dev, int *budget)
{
struct e1000_adapter *adapter;
int work_to_do = min(*budget, poll_dev->quota);
int tx_cleaned = 0, work_done = 0;
/* Must NOT use netdev_priv macro here. */
adapter = poll_dev->priv;
/* Keep link state information with original netdev */
if (!netif_carrier_ok(poll_dev))
goto quit_polling;
/* e1000_clean is called per-cpu. This lock protects
* tx_ring[0] from being cleaned by multiple cpus
* simultaneously. A failure obtaining the lock means
* tx_ring[0] is currently being cleaned anyway.
*
* ￥8 logic bug
*
* linux-2.6.20.7/drivers/net/e1000/e1000_main.c
*
* not-well-known pseudo TX-hang occurs
* in some cases when RX is busy enough.
*
*/
if (spin_trylock(&adapter->tx_queue_lock)) {
tx_cleaned = e1000_clean_tx_irq(adapter,
&adapter->tx_ring[0]);
spin_unlock(&adapter->tx_queue_lock);
}
adapter->clean_rx(adapter, &adapter->rx_ring[0],
&work_done, work_to_do);
*budget -= work_done;
poll_dev->quota -= work_done;
/* If no Tx and not enough Rx work done, exit the polling mode */
if ((!tx_cleaned && (work_done == 0)) ||
!netif_running(poll_dev)) {
quit_polling:
if (likely(adapter->itr_setting & 3))
e1000_set_itr(adapter);
netif_rx_complete(poll_dev);
e1000_irq_enable(adapter);
return 0;
}
return 1;
}

复制代码

--- linux-2.6.22.1/net/ipv4/ip_fragment.c 2007-07-11 02:56:30.000000000 +0800
+++ /usr/src/chg/ip_fragment3.c 2007-08-21 11:27:03.000000000 +0800
@@ -25,6 +25,7 @@
#include <linux/compiler.h>
#include <linux/module.h>
#include <linux/types.h>
+#include <linux/rcupdate.h>
#include <linux/mm.h>
#include <linux/jiffies.h>
#include <linux/skbuff.h>
@@ -111,8 +112,8 @@ int ip_frag_nqueues = 0;
static __inline__ void __ipq_unlink(struct ipq *qp)
{
- hlist_del(&qp->list);
- list_del(&qp->lru_list);
+ hlist_del_rcu(&qp->list);
+ list_del_rcu(&qp->lru_list);
ip_frag_nqueues--;
}
@@ -149,10 +150,10 @@ static void ipfrag_secret_rebuild(unsign
q->daddr, q->protocol);
if (hval != i) {
- hlist_del(&q->list);
+ hlist_del_rcu(&q->list);
/* Relink to new hash chain. */
- hlist_add_head(&q->list, &ipq_hash[hval]);
+ hlist_add_head_rcu(&q->list, &ipq_hash[hval]);
}
}
}
@@ -252,16 +253,16 @@ static void ip_evictor(void)
return;
while (work > 0) {
- read_lock(&ipfrag_lock);
+ rcu_read_lock();
if (list_empty(&ipq_lru_list)) {
- read_unlock(&ipfrag_lock);
+ rcu_read_unlock();
return;
}
- tmp = ipq_lru_list.next;
- qp = list_entry(tmp, struct ipq, lru_list);
+ tmp = rcu_dereference(ipq_lru_list.next);
+ qp = list_entry(tmp, struct ipq, lru_list);
atomic_inc(&qp->refcnt);
- read_unlock(&ipfrag_lock);
-
+ rcu_read_unlock();
+
spin_lock(&qp->lock);
if (!(qp->last_in&COMPLETE))
ipq_kill(qp);
@@ -320,7 +321,7 @@ static struct ipq *ip_frag_intern(struct
* such entry could be created on other cpu, while we
* promoted read lock to write lock.
*/
- hlist_for_each_entry(qp, n, &ipq_hash[hash], list) {
+ hlist_for_each_entry_rcu(qp, n, &ipq_hash[hash], list) {
if (qp->id == qp_in->id &&
qp->saddr == qp_in->saddr &&
qp->daddr == qp_in->daddr &&
@@ -340,9 +341,9 @@ static struct ipq *ip_frag_intern(struct
atomic_inc(&qp->refcnt);
atomic_inc(&qp->refcnt);
- hlist_add_head(&qp->list, &ipq_hash[hash]);
+ hlist_add_head_rcu(&qp->list, &ipq_hash[hash]);
INIT_LIST_HEAD(&qp->lru_list);
- list_add_tail(&qp->lru_list, &ipq_lru_list);
+ list_add_tail_rcu(&qp->lru_list, &ipq_lru_list);
ip_frag_nqueues++;
write_unlock(&ipfrag_lock);
return qp;
@@ -395,20 +396,20 @@ static inline struct ipq *ip_find(struct
struct ipq *qp;
struct hlist_node *n;
- read_lock(&ipfrag_lock);
+ rcu_read_lock();
hash = ipqhashfn(id, saddr, daddr, protocol);
- hlist_for_each_entry(qp, n, &ipq_hash[hash], list) {
+ hlist_for_each_entry_rcu(qp, n, &ipq_hash[hash], list) {
if (qp->id == id &&
qp->saddr == saddr &&
qp->daddr == daddr &&
qp->protocol == protocol &&
qp->user == user) {
atomic_inc(&qp->refcnt);
- read_unlock(&ipfrag_lock);
+ rcu_read_unlock();
return qp;
}
}
- read_unlock(&ipfrag_lock);
+ rcu_read_lock();
return ip_frag_create(iph, user);
}
@@ -599,7 +600,8 @@ static void ip_frag_queue(struct ipq *qp
qp->last_in |= FIRST_IN;
write_lock(&ipfrag_lock);
- list_move_tail(&qp->lru_list, &ipq_lru_list);
+ list_del_rcu(&qp->lru_list);
+ list_add_tail_rcu(&qp->lru_list, &ipq_lru_list);
write_unlock(&ipfrag_lock);
return;

复制代码

struct ip_conntrack
{
/* Usage count in here is 1 for hash table/destruct timer, 1 per skb,
plus 1 for any connection(s) we are `master' for */
struct nf_conntrack ct_general;
/* Have we seen traffic both ways yet? (bitset) */
unsigned long status;
/* Timer function; drops refcnt when it goes off. */
/*
* linux-2.6.20.7/include/linux/netfilter_ipv4/ip_conntrack.h
* ￥8
* potential vulnerability in design
*
* if as boasted, FW warrant 1M connections,
* how many cpus required to response timer?
*/
struct timer_list timeout;
#ifdef CONFIG_IP_NF_CT_ACCT
/* Accounting Information (same cache line as other written members) */
struct ip_conntrack_counter counters[IP_CT_DIR_MAX];
#endif
/* If we were expected by an expectation, this will be it */
struct ip_conntrack *master;
/* Current number of expected connections */
unsigned int expecting;
/* Unique ID that identifies this conntrack*/
unsigned int id;
/* Helper, if any. */
struct ip_conntrack_helper *helper;
/* Storage reserved for other modules: */
union ip_conntrack_proto proto;
union ip_conntrack_help help;
#ifdef CONFIG_IP_NF_NAT_NEEDED
struct {
struct ip_nat_info info;
union ip_conntrack_nat_help help;
#if defined(CONFIG_IP_NF_TARGET_MASQUERADE) || \
defined(CONFIG_IP_NF_TARGET_MASQUERADE_MODULE)
int masq_index;
#endif
} nat;
#endif /* CONFIG_IP_NF_NAT_NEEDED */
#if defined(CONFIG_IP_NF_CONNTRACK_MARK)
u_int32_t mark;
#endif
#ifdef CONFIG_IP_NF_CONNTRACK_SECMARK
u_int32_t secmark;
#endif
/* Traversed often, so hopefully in different cacheline to top */
/* These are my tuples; original and reply */
struct ip_conntrack_tuple_hash tuplehash[IP_CT_DIR_MAX];
};

复制代码

void shrink_dcache_sb(struct super_block * sb)
{
struct list_head *tmp, *next;
struct dentry *dentry;
/*
* Pass one ... move the dentries for the specified
* superblock to the most recent end of the unused list.
*/
spin_lock(&dcache_lock);
list_for_each_safe(tmp, next, &dentry_unused) {
dentry = list_entry(tmp, struct dentry, d_lru);
if (dentry->d_sb != sb)
continue;
list_move(tmp, &dentry_unused);
}
/*
* Pass two ... free the dentries for this superblock.
*/
repeat:
list_for_each_safe(tmp, next, &dentry_unused) {
dentry = list_entry(tmp, struct dentry, d_lru);
if (dentry->d_sb != sb)
continue;
dentry_stat.nr_unused--;
list_del_init(tmp);
spin_lock(&dentry->d_lock);
if (atomic_read(&dentry->d_count)) {
/*
* linux-2.6.20.7/fs/dcache.c
*
* ￥3
* how can i get dentry on lru later?
* where u go on earth?
*/
spin_unlock(&dentry->d_lock);
continue;
}
prune_one_dentry(dentry);
cond_resched_lock(&dcache_lock);
goto repeat;
}
spin_unlock(&dcache_lock);
}

复制代码

int ocfs2_node_map_is_only(struct ocfs2_super *osb,
struct ocfs2_node_map *target,
int bit)
{
struct ocfs2_node_map temp;
int ret;
spin_lock(&osb->node_map_lock);
__ocfs2_node_map_dup(&temp, target);
/*
* linux-2.6.20.7/fs/ocfs2/heartbeat.c
*
* ￥1
*
* abuse of spin_lock
*/
__ocfs2_node_map_clear_bit(&temp, bit);
ret = __ocfs2_node_map_is_empty(&temp);
spin_unlock(&osb->node_map_lock);
return ret;
}

复制代码

int ocfs2_node_map_iterate(struct ocfs2_super *osb,
struct ocfs2_node_map *map,
int idx)
{
int i = idx;
idx = O2NM_INVALID_NODE_NUM;
spin_lock(&osb->node_map_lock);
if ((i != O2NM_INVALID_NODE_NUM) &&
(i >= 0) &&
(i < map->num_nodes)) {
/*
* linux-2.6.20.7/fs/ocfs2/heartbeat.c
*
* ￥1
*
* oversight bitops of arch version by linux
*/
while (i < map->num_nodes) {
if (test_bit(i, map->map)) {
idx = i;
break;
}
i++;
}
}
spin_unlock(&osb->node_map_lock);
return idx;
}

复制代码

int vfs_rmdir(struct inode *dir, struct dentry *dentry)
{
int error = may_delete(dir, dentry, 1);
if (error)
return error;
if (!dir->i_op || !dir->i_op->rmdir)
return -EPERM;
DQUOT_INIT(dir);
mutex_lock(&dentry->d_inode->i_mutex);
dentry_unhash(dentry);
if (d_mountpoint(dentry))
error = -EBUSY;
else {
error = security_inode_rmdir(dir, dentry);
if (!error) {
error = dir->i_op->rmdir(dir, dentry);
if (!error)
dentry->d_inode->i_flags |= S_DEAD;
}
}
mutex_unlock(&dentry->d_inode->i_mutex);
if (!error) {
/*
* linux-2.6.20.7/fs/namei.c
*
* potentially trigger-1
*/
d_delete(dentry);
}
dput(dentry);
return error;
}

复制代码

void d_delete(struct dentry * dentry)
{
int isdir = 0;
/*
* Are we the only user?
*/
spin_lock(&dcache_lock);
spin_lock(&dentry->d_lock);
isdir = S_ISDIR(dentry->d_inode->i_mode);
if (atomic_read(&dentry->d_count) == 1) {
dentry_iput(dentry);
fsnotify_nameremove(dentry, isdir);
/* remove this and other inotify debug checks after 2.6.18 */
dentry->d_flags &= ~DCACHE_INOTIFY_PARENT_WATCHED;
/*
* linux-2.6.20.7/fs/dcache.c
*
* potentially trigger-2
*/
return;
}
if (!d_unhashed(dentry))
__d_drop(dentry);
spin_unlock(&dentry->d_lock);
spin_unlock(&dcache_lock);
fsnotify_nameremove(dentry, isdir);
}

复制代码

void dput(struct dentry *dentry)
{
if (!dentry)
return;
repeat:
if (atomic_read(&dentry->d_count) == 1)
might_sleep();
if (!atomic_dec_and_lock(&dentry->d_count, &dcache_lock))
return;
/*
* linux-2.6.20.7/fs/dcache.c
*
* ￥6
* potentially race @ here
*/
spin_lock(&dentry->d_lock);
if (atomic_read(&dentry->d_count)) {
spin_unlock(&dentry->d_lock);
spin_unlock(&dcache_lock);
return;
}
/*
* AV: ->d_delete() is _NOT_ allowed to block now.
*/
if (dentry->d_op && dentry->d_op->d_delete) {
if (dentry->d_op->d_delete(dentry))
goto unhash_it;
}
/* Unreachable? Get rid of it */
if (d_unhashed(dentry))
goto kill_it;
if (list_empty(&dentry->d_lru)) {
dentry->d_flags |= DCACHE_REFERENCED;
list_add(&dentry->d_lru, &dentry_unused);
dentry_stat.nr_unused++;
}
spin_unlock(&dentry->d_lock);
spin_unlock(&dcache_lock);
return;
unhash_it:
__d_drop(dentry);
kill_it: {
struct dentry *parent;
/* If dentry was on d_lru list,
* delete it from there
*/
if (!list_empty(&dentry->d_lru)) {
list_del(&dentry->d_lru);
dentry_stat.nr_unused--;
}
list_del(&dentry->d_u.d_child);
dentry_stat.nr_dentry--; /* For d_free, below */
/* drops the locks,
* at that point nobody can reach this dentry
*/
dentry_iput(dentry);
parent = dentry->d_parent;
d_free(dentry);
if (dentry == parent)
return;
dentry = parent;
goto repeat;
}
}

复制代码

void dput(struct dentry *dentry)
{
if (!dentry)
return;
repeat:
if (atomic_read(&dentry->d_count) == 1)
might_sleep();
if (!atomic_dec_and_lock(&dentry->d_count, &dcache_lock))
return;
/*
* linux-2.6.20.7/fs/dcache.c
*
* ￥6
* potentially race @ here
*/
spin_lock(&dentry->d_lock);
if (atomic_read(&dentry->d_count)) {
spin_unlock(&dentry->d_lock);
spin_unlock(&dcache_lock);
return;
}
/*
* AV: ->d_delete() is _NOT_ allowed to block now.
*/
if (dentry->d_op && dentry->d_op->d_delete) {
if (dentry->d_op->d_delete(dentry))
goto unhash_it;
}
/* Unreachable? Get rid of it */
if (d_unhashed(dentry))
goto kill_it;
if (list_empty(&dentry->d_lru)) {
dentry->d_flags |= DCACHE_REFERENCED;
list_add(&dentry->d_lru, &dentry_unused);
dentry_stat.nr_unused++;
}
spin_unlock(&dentry->d_lock);
spin_unlock(&dcache_lock);
return;
unhash_it:
__d_drop(dentry);
kill_it: {
struct dentry *parent;
/* If dentry was on d_lru list,
* delete it from there
*/
if (!list_empty(&dentry->d_lru)) {
list_del(&dentry->d_lru);
dentry_stat.nr_unused--;
}
list_del(&dentry->d_u.d_child);
dentry_stat.nr_dentry--; /* For d_free, below */
/* drops the locks,
* at that point nobody can reach this dentry
*/
dentry_iput(dentry);
parent = dentry->d_parent;
d_free(dentry);
if (dentry == parent)
return;
dentry = parent;
goto repeat;
}
}

复制代码

if (!error) {
d_delete(dentry);
/*
* d_delete return potentially without releasing dcache_lock & dentry->d_lock
*/
}
/*
* however dput at least try to get dentry->d_lock
*/
dput(dentry);
/*
* yeah, these codes used everyday after bootstrap,
* why not heard bloat???
*/

复制代码

/*
* linux-2.6.20.7/fs/dcache.c
*/
static void dentry_iput(struct dentry * dentry)
{
struct inode * inode = dentry->d_inode;
if (inode) {
dentry->d_inode = NULL;
list_del_init(&dentry->d_alias);
spin_unlock(&dentry->d_lock);
spin_unlock(&dcache_lock);
if (!inode->i_nlink)
fsnotify_inoderemove(inode);
if (dentry->d_op && dentry->d_op->d_iput)
dentry->d_op->d_iput(dentry, inode);
else
iput(inode);
} else {
spin_unlock(&dentry->d_lock);
spin_unlock(&dcache_lock);
}
}

复制代码

int tcp_set_allowed_congestion_control(char *val)
{
.............
out:
spin_unlock(&tcp_cong_list_lock);
if (clone)
kfree(clone);
return ret;
}
/*
* based upon linux/2.6.20.7/mm/utils.c
*/
char * kstrdup(const char *s, gfp_t gfp)
{
size_t len;
char *buf;
if (!s)
return NULL;
len = strlen(s) + 1;
buf = kmalloc_track_caller(len, gfp);
if (buf)
memcpy(buf, s, len);
return buf;
}

复制代码

int tcp_set_allowed_congestion_control(char *val)
{
struct tcp_congestion_ops *ca;
char *clone, *name;
+ char *org;
int ret = 0;
clone = kstrdup(val, GFP_USER);
if (!clone)
return -ENOMEM;
+ org = clone;
spin_lock(&tcp_cong_list_lock);
/* pass 1 check for bad entries */
while ((name = strsep(&clone, " ")) && *name) {
ca = tcp_ca_find(name);
if (!ca) {
ret = -ENOENT;
goto out;
}
}
/* pass 2 clear old values */
list_for_each_entry_rcu(ca, &tcp_cong_list, list)
ca->flags &= ~TCP_CONG_NON_RESTRICTED;
/* pass 3 mark as allowed */
while ((name = strsep(&val, " ")) && *name) {
ca = tcp_ca_find(name);
WARN_ON(!ca);
if (ca)
ca->flags |= TCP_CONG_NON_RESTRICTED;
}
out:
spin_unlock(&tcp_cong_list_lock);
+ if (org) kfree(org);
return ret;
}

复制代码

static ssize_t dlmfs_file_read(struct file *filp,
char __user *buf, size_t count,
loff_t *ppos)
{
int bytes_left;
ssize_t readlen;
char *lvb_buf;
struct inode *inode = filp->f_path.dentry->d_inode;
mlog(0, "inode %lu, count = %zu, *ppos = %llu\n",
inode->i_ino, count, *ppos);
if (*ppos >= i_size_read(inode))
return 0;
if (!count)
return 0;
if (!access_ok(VERIFY_WRITE, buf, count))
return -EFAULT;
/* don't read past the lvb */
if ((count + *ppos) > i_size_read(inode))
readlen = i_size_read(inode) - *ppos;
else
/*
* linux-2.6.22.5/fs/ocfs2/dlm/dlmfs.c
* ￥2
* what relation between count and ppos?
* readlen determined right?
* say, i_size_read(inode) = 8M bytes, count = 4096 bytes.
*/
readlen = count - *ppos;
lvb_buf = kmalloc(readlen, GFP_NOFS);
if (!lvb_buf)
return -ENOMEM;
user_dlm_read_lvb(inode, lvb_buf, readlen);
bytes_left = __copy_to_user(buf, lvb_buf, readlen);
readlen -= bytes_left;
kfree(lvb_buf);
*ppos = *ppos + readlen;
mlog(0, "read %zd bytes\n", readlen);
return readlen;
}

复制代码

static ssize_t dlmfs_file_write(struct file *filp,
const char __user *buf, size_t count,
loff_t *ppos)
{
int bytes_left;
ssize_t writelen;
char *lvb_buf;
struct inode *inode = filp->f_path.dentry->d_inode;
mlog(0, "inode %lu, count = %zu, *ppos = %llu\n",
inode->i_ino, count, *ppos);
if (*ppos >= i_size_read(inode))
return -ENOSPC;
if (!count)
return 0;
if (!access_ok(VERIFY_READ, buf, count))
return -EFAULT;
/* don't write past the lvb */
if ((count + *ppos) > i_size_read(inode))
writelen = i_size_read(inode) - *ppos;
else
/*
* linux-2.6.22.5/fs/ocfs2/dlm/dlmfs.c
#!/bin/sh
if [ $# != 2 ]
then
echo disasfun objectfile functionname
exit 1
fi
OBJFILE=$1
FUNNAME=$2
ADDRSZ=`objdump -t $OBJFILE | gawk -- "{
if (\\\$3 == \\"F\\" && \\\$6 == \\"$FUNNAME\\") {
printf(\\"%s %s\\", \\\$1, \\\$5)
}
}"`
ADDR=`echo $ADDRSZ | gawk "{ printf(\\"%s\\",\\\$1)}"`
SIZE=`echo $ADDRSZ | gawk "{ printf(\\"%s\\",\\\$2)}"`
if [ -z "$ADDR" -o -z "$SIZE" ]
then
echo Cannot find address or size of function $FUNNAME
exit 2
fi
objdump -S $OBJFILE --start-address=0x$ADDR --stop-address=$((0x$ADDR + 0x$SIZE))
* writelen determined right?
*/
writelen = count - *ppos;
lvb_buf = kmalloc(writelen, GFP_NOFS);
if (!lvb_buf)
return -ENOMEM;
bytes_left = copy_from_user(lvb_buf, buf, writelen);
writelen -= bytes_left;
if (writelen)
user_dlm_write_lvb(inode, lvb_buf, writelen);
kfree(lvb_buf);
*ppos = *ppos + writelen;
mlog(0, "wrote %zd bytes\n", writelen);
return writelen;
}

复制代码

static int ocfs2_write_data_page(struct inode *inode, handle_t *handle,
u64 *p_blkno, struct page *page,
struct ocfs2_write_ctxt *wc, int new)
{
int ret, copied = 0;
unsigned int from = 0, to = 0;
unsigned int cluster_start, cluster_end;
unsigned int zero_from = 0, zero_to = 0;
ocfs2_figure_cluster_boundaries(OCFS2_SB(inode->i_sb), wc->w_cpos,
&cluster_start, &cluster_end);
if ((wc->w_pos >> PAGE_CACHE_SHIFT) == page->index
&& !wc->w_finished_copy) {
wc->w_this_page = page;
wc->w_this_page_new = new;
ret = wc->w_write_data_page(inode, wc, p_blkno, &from, &to);
if (ret < 0) {
mlog_errno(ret);
goto out;
}
copied = ret;
zero_from = from;
zero_to = to;
if (new) {
from = cluster_start;
to = cluster_end;
}
} else {
/*
* If we haven't allocated the new page yet, we
* shouldn't be writing it out without copying user
* data. This is likely a math error from the caller.
*/
BUG_ON(!new);
from = cluster_start;
to = cluster_end;
ret = ocfs2_map_page_blocks(page, p_blkno, inode,
cluster_start, cluster_end, 1);
if (ret) {
mlog_errno(ret);
goto out;
}
}
/*
* Parts of newly allocated pages need to be zero'd.
*
* Above, we have also rewritten 'to' and 'from' - as far as
* the rest of the function is concerned, the entire cluster
* range inside of a page needs to be written.
*
* We can skip this if the page is uptodate - it's already
* been zero'd from being read in as a hole.
*/
if (new && !PageUptodate(page))
ocfs2_clear_page_regions(page, OCFS2_SB(inode->i_sb),
wc->w_cpos, zero_from, zero_to);
flush_dcache_page(page);
if (ocfs2_should_order_data(inode)) {
ret = walk_page_buffers(handle,
page_buffers(page),
from, to, NULL,
ocfs2_journal_dirty_data);
if (ret < 0)
/*
* linux-2.6.22.5/fs/ocfs2/aops.c
*
* how to & necessary to include this case on return?
* how to re-check in mlog?
*/
mlog_errno(ret);
}
/*
* We don't use generic_commit_write() because we need to
* handle our own i_size update.
*/
ret = block_commit_write(page, from, to);
if (ret)
mlog_errno(ret);
out:
return copied ? copied : ret;
}

复制代码

static int ocfs2_try_to_merge_extent_map(struct ocfs2_extent_map_item *emi,
struct ocfs2_extent_map_item *ins)
{
/*
* Handle contiguousness
*/
if (ins->ei_phys == (emi->ei_phys + emi->ei_clusters) &&
ins->ei_cpos == (emi->ei_cpos + emi->ei_clusters) &&
ins->ei_flags == emi->ei_flags) {
emi->ei_clusters += ins->ei_clusters;
return 1;
} else if ((ins->ei_phys + ins->ei_clusters) == emi->ei_phys &&
/*
* linux-2.6.22.5/fs/ocfs2/extent_map.c
* why not
* (ins->ei_cpos + ins->ei_clusters) == emi->ei_cpos
* and more symmetric??
*/
(ins->ei_cpos + ins->ei_clusters) == emi->ei_phys &&
ins->ei_flags == emi->ei_flags) {
emi->ei_phys = ins->ei_phys;
emi->ei_cpos = ins->ei_cpos;
emi->ei_clusters += ins->ei_clusters;
return 1;
}
/*
* Overlapping extents - this shouldn't happen unless we've
* split an extent to change it's flags. That is exceedingly
* rare, so there's no sense in trying to optimize it yet.
*/
if (ocfs2_ei_is_contained(emi, ins) ||
ocfs2_ei_is_contained(ins, emi)) {
/*
* more care needed in em-cache, even a small/simple one.
*/
ocfs2_copy_emi_fields(emi, ins);
return 1;
}
/* No merge was possible. */
return 0;
}

复制代码

/* linux-2.6.22.5/arch/i386/kernel/io_apic.c */
static void __init setup_IO_APIC_irqs (void)
{
entry.trigger = irq_trigger(idx);
entry.polarity = irq_polarity(idx);
/*2007-12-1 18:29
if (entry.trigger) {
entry.mask = 1;
}
*/
if (irq_trigger(idx)) {
entry.trigger = 1;
entry.mask = 1;
}
irq = pin_2_irq(idx, apic, pin);
}

复制代码

void set_pending_irq(unsigned int irq, cpumask_t mask)
{
struct irq_desc *desc = irq_desc + irq;
unsigned long flags;
spin_lock_irqsave(&desc->lock, flags);
desc->status |= IRQ_MOVE_PENDING;
/* 2007-12-8 7:50
* linux-2.6.22.5/kernel/irq/migration.c
* desc->pending_mask = mask;
*/
irq_desc[irq].pending_mask = mask;
spin_unlock_irqrestore(&desc->lock, flags);
}

复制代码

Touching APIC represented by GNU linux-2.6.22+

复制代码

#ifndef _LINUX_IRQ_H
#define _LINUX_IRQ_H
/*
* Please do not include this file in generic code.
*
* There is currently no requirement for any architecture
* to implement anything held within this file.
*
* Thanks. --rmk
*
××××××××××××××××××××××××××××××××××××
* IRQ的处理，Ingo Molnar是大今天的赢家，
* 2.6.21+ 迎来Ingo Molnar的时代，还有Andi Kleen in X86-64.
*
* 这种统一的设计方法，俺八哥百学不会，汗汗汗，
× 类似的经典
* VFS,
* Block, 老鸟 Jens Axboe, Andrea Arcangeli
* Socket, 新秀 Arnaldo Carvalho de Melo
× Netfilter, 新秀 Yasuyuki Kozakai的时代
××××××××××××××××××××××××××××××××××××
×
× 2007/9--11月，八哥出京躲债，在APIC上吃了亏，今天想把这一课补上。
* IRQ，软件的基本定义从<linux/irq.h>发源，
× 硬件已经是XAPIC的时代，八哥想介绍几个关系，
* 1, vector[IRQ]
* 2, LAPIC[IRQ]/IOPIC[IRQ]
* 3, cpu-balance[IRQ]
* 4, request[IRQ]
*
* 代码来自linux-2.6.22.5 from kernel.org
*/
request[IRQ]
============
先看熟悉的，菜鸟八哥这里仅限于PCI，
request[IRQ]是IRQ subsystem给device driver提供的接口，
static int e1000_request_irq (struct e1000_adapter *adapter)
{
struct net_device *netdev = adapter->netdev;
void (*handler) = &e1000_intr;
int irq_flags = IRQF_SHARED;
int err;
if (adapter->hw.mac_type >= e1000_82571) {
adapter->have_msi = !pci_enable_msi(adapter->pdev);
if (adapter->have_msi) {
handler = &e1000_intr_msi;
irq_flags = 0;
}
}
err = request_irq(adapter->pdev->irq, handler,
irq_flags, netdev->name, netdev);
if (err) {
if (adapter->have_msi)
pci_disable_msi(adapter->pdev);
DPRINTK(PROBE, ERR,
"Unable to allocate interrupt Error: %d\n", err);
}
return err;
}
设备/芯片的属性/能力不同，表现在request[IRQ]的操作上，
1，msi与non-msi两种模式
[homework]
if (adapter->hw.mac_type >= e1000_82571) {
adapter->have_msi = !pci_enable_msi(adapter->pdev);
if (adapter->have_msi) {
handler = &e1000_intr_msi;
irq_flags = 0;
}
} else
irq_flags = 0;
又如何？
[/homework]
[homework]
falgs 的定义在 <linux/interrupt.h>
请比较
flags |= IRQF_DISABLED ;
request_irq();
与
flags ~= IRQF_DISABLED ;
request_irq();
的do_IRQ的上下文的区别，扯远啦。
[/homework]
2，handler统吃两种模式，够牛吧，
非兮，应该是硬件支持。
int pci_enable_msi (struct pci_dev *dev)
{
int status;
status = pci_msi_check_device(dev, 1, PCI_CAP_ID_MSI);
if (status)
return status;
WARN_ON(!!dev->msi_enabled);
/* Check whether driver already requested for MSI-X irqs */
///
/// nnd, MSI还没整明白，MSI-X又冒出来了，
/// 三天不学习，赶不上刘少奇
///
if (dev->msix_enabled) {
printk(KERN_INFO "PCI: %s: Can't enable MSI. "
"Device already has MSI-X enabled\n",
pci_name(dev));
return -EINVAL;
}
status = msi_capability_init(dev);
return status;
}
static int pci_msi_check_device (struct pci_dev* dev, int nvec, int type)
{
struct pci_bus *bus;
int ret;
/* MSI must be globally enabled and supported by the device */
///
///其一，CONFIG_MSI
///
if (!pci_msi_enable || !dev || dev->no_msi)
return -EINVAL;
/*
* You can't ask to have 0 or less MSIs configured.
* a) it's stupid ..
* b) the list manipulation code assumes nvec >= 1.
*/
if (nvec < 1)
return -ERANGE;
/* Any bridge which does NOT route MSI transactions from it's
* secondary bus to it's primary bus must set NO_MSI flag on
* the secondary pci_bus.
* We expect only arch-specific PCI host bus controller driver
* or quirks for specific PCI bridges to be setting NO_MSI.
*/
///
///其二，要求芯片组上下贯通，丝毫不含糊
///
for (bus = dev->bus; bus; bus = bus->parent)
if (bus->bus_flags & PCI_BUS_FLAGS_NO_MSI)
return -EINVAL;
///
///其三，查询其他要求
///
ret = arch_msi_check_device(dev, nvec, type);
if (ret)
return ret;
///
///其四，设备要有能力
///
if (!pci_find_capability(dev, type))
return -EINVAL;
return 0;
}
3，pdev->irq 哪来的？
static void __init pdev_fixup_irq (struct pci_dev *dev,
u8 (*swizzle)(struct pci_dev *, u8 *),
int (*map_irq)(struct pci_dev *, u8, u8))
{
u8 pin, slot;
int irq = 0;
/*
If this device is not on the primary bus,
we need to figure out which interrupt pin it will come in on.
We know which slot it will come in on 'cos that slot is where the bridge is.
Each time the interrupt line passes through a PCI-PCI bridge we must
apply the swizzle function.
*/
pci_read_config_byte(dev, PCI_INTERRUPT_PIN, &pin);
/* Cope with illegal */
if (pin > 4)
pin = 1;
if (pin != 0) {
/* Follow the chain of bridges, swizzling as we go. */
slot = (*swizzle)(dev, &pin);
irq = (*map_irq)(dev, slot, pin);
if (irq == -1)
irq = 0;
}
///
///其二，原来如此
/// pci dev 在PCI空间是 bus:slot.fun
/// 在APCI空间是 bus:slot.pin，这是后话
/***
static void pci_read_irq (struct pci_dev *dev)
{
unsigned char irq;
pci_read_config_byte(dev, PCI_INTERRUPT_PIN, &irq);
dev->pin = irq;
if (irq)
pci_read_config_byte(dev, PCI_INTERRUPT_LINE, &irq);
///
///其三，PCI_INTERRUPT_PIN 与PCI_INTERRUPT_LINE的统一
///
dev->irq = irq;
}
***/
dev->irq = irq;
pr_debug("PCI: fixup irq: (%s) got irq%d\n",
dev->dev.kobj.name, dev->irq);
/* Always tell the device, so the driver knows what is
the real IRQ to use; the device does not use it.
*/
pcibios_update_irq(dev, irq);
}
void __init pci_fixup_irqs (u8 (*swizzle)(struct pci_dev *, u8 *),
int (*map_irq)(struct pci_dev *, u8, u8))
{
struct pci_dev *dev = NULL;
///
///其一，都在这了，呵呵
///
while ((dev = pci_get_device(PCI_ANY_ID, PCI_ANY_ID, dev)) != NULL) {
pdev_fixup_irq(dev, swizzle, map_irq);
}
}
[homework]
MSI的IRQ如何不同，有的驱动在这儿就没有留心。
[/homework]

复制代码

vector[IRQ]
===========
Understanding 有一章介绍Vector和IDT(Interrupt Description Table),
八哥看的是第二版，其基本定义在
#ifndef _ASM_HW_IRQ_H
#define _ASM_HW_IRQ_H
/*
* linux/include/asm/hw_irq.h
*
* (C) 1992, 1993 Linus Torvalds, (C) 1997 Ingo Molnar
*
* moved some of the old arch/i386/kernel/irq.h to here. VY
*
* IRQ/IPI changes taken from work by Thomas Radke
* <[email]tomsoft@informatik.tu-chemnitz.de[/email]>
*
* hacked by Andi Kleen for x86-64
*/
相对i386，x86-64的情况简单些，
#define NMI_VECTOR 0x02
/*
* IDT vectors usable for external interrupt sources start
* at 0x20:
×
× 0x00--0x1f被处理器占用，in kernel/traps.c
void __init trap_init(void)
{
set_intr_gate(0,&divide_error);
set_intr_gate_ist(1,&debug,DEBUG_STACK);
set_intr_gate_ist(2,&nmi,NMI_STACK);
set_system_gate_ist(3,&int3,DEBUG_STACK); /* int3 can be called from all */
set_system_gate(4,&overflow); /* int4 can be called from all */
set_intr_gate(5,&bounds);
set_intr_gate(6,&invalid_op);
set_intr_gate(7,&device_not_available);
set_intr_gate_ist(8,&double_fault, DOUBLEFAULT_STACK);
set_intr_gate(9,&coprocessor_segment_overrun);
set_intr_gate(10,&invalid_TSS);
set_intr_gate(11,&segment_not_present);
set_intr_gate_ist(12,&stack_segment,STACKFAULT_STACK);
set_intr_gate(13,&general_protection);
set_intr_gate(14,&page_fault);
set_intr_gate(15,&spurious_interrupt_bug);
set_intr_gate(16,&coprocessor_error);
set_intr_gate(17,&alignment_check);
#ifdef CONFIG_X86_MCE
set_intr_gate_ist(18,&machine_check, MCE_STACK);
#endif
set_intr_gate(19,&simd_coprocessor_error);
#ifdef CONFIG_IA32_EMULATION
set_system_gate(IA32_SYSCALL_VECTOR, ia32_syscall);
#endif
/*
* Should be a barrier for any external CPU state.
*/
cpu_init();
}
×××××××××××××
*/
#define FIRST_EXTERNAL_VECTOR 0x20
#define IA32_SYSCALL_VECTOR 0x80
/* Reserve the lowest usable priority level 0x20 - 0x2f for triggering
* cleanup after irq migration.
*/
#define IRQ_MOVE_CLEANUP_VECTOR FIRST_EXTERNAL_VECTOR
/*
* Vectors 0x30-0x3f are used for ISA interrupts.
*
* 所谓的16个legacy IRQ被映射到vector[0x30--0x3f]
*/
#define IRQ0_VECTOR FIRST_EXTERNAL_VECTOR + 0x10 ///0x20 + 0x10 = 0x30
#define IRQ1_VECTOR IRQ0_VECTOR + 1
#define IRQ2_VECTOR IRQ0_VECTOR + 2
#define IRQ3_VECTOR IRQ0_VECTOR + 3
#define IRQ4_VECTOR IRQ0_VECTOR + 4
#define IRQ5_VECTOR IRQ0_VECTOR + 5
#define IRQ6_VECTOR IRQ0_VECTOR + 6
#define IRQ7_VECTOR IRQ0_VECTOR + 7
#define IRQ8_VECTOR IRQ0_VECTOR + 8
#define IRQ9_VECTOR IRQ0_VECTOR + 9
#define IRQ10_VECTOR IRQ0_VECTOR + 10
#define IRQ11_VECTOR IRQ0_VECTOR + 11
#define IRQ12_VECTOR IRQ0_VECTOR + 12
#define IRQ13_VECTOR IRQ0_VECTOR + 13
#define IRQ14_VECTOR IRQ0_VECTOR + 14
#define IRQ15_VECTOR IRQ0_VECTOR + 15
/*
* Special IRQ vectors used by the SMP architecture, 0xf0-0xff
*
* some of the following vectors are 'rare', they are merged
* into a single vector (CALL_FUNCTION_VECTOR) to save vector space.
*
* TLB, reschedule and local APIC vectors are performance-critical.
*/
#define SPURIOUS_APIC_VECTOR 0xff
#define ERROR_APIC_VECTOR 0xfe
#define RESCHEDULE_VECTOR 0xfd
#define CALL_FUNCTION_VECTOR 0xfc
/*
0xfb free - please don't re-add KDB here because it's useless
(hint - think what a NMI bit does to a vector)
*/
#define THERMAL_APIC_VECTOR 0xfa
#define THRESHOLD_APIC_VECTOR 0xf9
/*
0xf8 free
*/
#define INVALIDATE_TLB_VECTOR_END 0xf7
#define INVALIDATE_TLB_VECTOR_START 0xf0 /* 0xf0--0xf7 used for TLB flush */
#define NUM_INVALIDATE_TLB_VECTORS 8 /* 0xf0--0xf7 */
/*
* Local APIC timer IRQ vector is on a different priority level,
* to work around the 'lost local interrupt if more than 2 IRQ
* sources per level' errata.
*/
#define LOCAL_TIMER_VECTOR 0xef
/*
* First APIC vector available to drivers: (vectors 0x30-0xee)
* we start at 0x41 to spread out vectors evenly between priority
* levels. (0x80 is the syscall vector)
*
* 有了vector和IRQ的映射关系，还要主意 priority levels.
*/
#define FIRST_DEVICE_VECTOR (IRQ15_VECTOR + 2)
#define FIRST_SYSTEM_VECTOR 0xef /* duplicated in irq.h */
#ifndef __ASSEMBLY__
typedef int vector_irq_t[NR_VECTORS];
DECLARE_PER_CPU(vector_irq_t, vector_irq);
/*
* 映射关系的具体实现，int[NR_CPUS][NR_VECTORS];
*/
extern void __setup_vector_irq(int cpu);
/*
* 映射关系的操作方法
*/
extern spinlock_t vector_lock;
/*
* Various low-level irq details needed by
* irq.c,
* process.c,
* time.c,
* io_apic.c and
* smp.c
*
* 如此多，如此诱惑的金矿，镐在哪？
*
* Interrupt entry/exit code at both C and assembly level
*/
extern void disable_8259A_irq(unsigned int irq);
extern void enable_8259A_irq(unsigned int irq);
/*
* 8259A的系列操作
*/
extern int i8259A_irq_pending(unsigned int irq);
extern void make_8259A_irq(unsigned int irq);
extern void init_8259A(int aeoi);
extern void send_IPI(int dest, int vector);
/*
* IPI, inter-processor interrupt 操作
*
[homework]
搜出所有的IPI操作，under arch/x86_64,
仔细揣摩，玩法多多。
[/homework]
*/
extern void send_IPI_self(int vector);
extern void init_VISWS_APIC_irqs(void);
extern void setup_IO_APIC(void);
extern void disable_IO_APIC(void);
/*
* IO_APIC的系列操作，后文慢慢说
*/
extern void print_IO_APIC(void);
extern int IO_APIC_get_PCI_irq_vector(int bus, int slot, int fn);
extern void setup_ioapic_dest(void);
extern unsigned long io_apic_irqs;
extern atomic_t irq_err_count;
extern atomic_t irq_mis_count;
/*
io_apic_irqs 是 bitmap??
*/
#define IO_APIC_IRQ(x) (((x) >= 16) || ((1<<(x)) & io_apic_irqs))
#define __STR(x) #x
#define STR(x) __STR(x)
#include <asm/ptrace.h>
#define IRQ_NAME2(nr) nr##_interrupt(void)
#define IRQ_NAME(nr) IRQ_NAME2(IRQ##nr)
/*
* SMP has a few special interrupts for IPI messages
*
* 请说明 #define BUILD_IRQ(nr)
*/
#define BUILD_IRQ(nr) \
asmlinkage void IRQ_NAME(nr); \
__asm__("\n.p2align\n" \
"IRQ" #nr "_interrupt:\n\t" \
"push $~(" #nr ") ; " \
"jmp common_interrupt");
#define platform_legacy_irq(irq) ((irq) < 16)
#endif
#endif /* _ASM_HW_IRQ_H */
///
///中断发生时，vector 的操作在 arch/kernel/head.S
///vector[IRQ]如何填充？？
///

复制代码

APIC[IRQ]
=========
#ifndef __ASM_APICDEF_H
#define __ASM_APICDEF_H
/*
* Constants for various Intel APICs. (local APIC, IOAPIC, etc.)
*
* Alan Cox <[email]Alan.Cox@linux.org[/email]>, 1995.
* Ingo Molnar <[email]mingo@redhat.com[/email]>, 1999, 2000
*/
#define MAX_IO_APICS 128
#define MAX_LOCAL_APIC 256
///
/// APIC = Local APIC + IO APIC
/// 相比 IO APIC，LAPIC要简单些，
/// 软件描述为 struct local_apic。
///
/// 多处理器环境，cpu = smp_processor_id();
/// boot_cpu = 0; 这是逻辑编号；还有phy_cpu_id[cpu]编号。
///
/// 在APIC空间，phy_lapic_id[nr], 0 <= nr < MAX_LOCAL_APIC,
/// cpu还有与nr的映射关系，cpu = lapic_cpu[nr]。
///
/// 八哥从来不看Manul, either Intel or AMD,
/// 实话是看不懂，只在代码里面体会。
/// 这里摘录Understanding-II，
/// 1，CPU包含一部分called LAPIC
/// 2，LAPIC包含：
/// 一堆寄存器 /* in struct local_apic */
/// 一个内部时钟
/// LINT0/1
///
/// 3, IOAPIC包含：
/// N条IRQ线
/// N项IRT，interrupt routing/redirection table
/// IRT可以被独立编程，指明
/// 中断向量
/// 优先级
/// 目标处理器 /* represented by lapic */
/// 选择处理器的方式
///
/// 4, 中断的分发方式
/// 4.1 静态分发
/// 查IRT中设定的LAPIC，可以是一个CPU，多个CPU, 全部CPU。
///
/// 4.2 动态分发
/// 4.2.1 根据正在运行的进程的优先级，发送给低优先级。
/// 因为LAPIC有可编程TPR，task priority register.
/// 4.2.2 优先级不能决定时，由arbitration决定。
///
/// 5，通过写LAPIC的ICR，interrupt command register,
/// 产生IPI，inter-processor interrupt
///
/// APIC的着眼点是P，在代码中领会，
/// LAPIC的中断分发，IOAPIC的IRT。
///
/*
* All x86-64 systems are xAPIC compatible.
* In the following, "apicid" is a physical APIC ID.
*/
#define XAPIC_DEST_CPUS_SHIFT 4
#define XAPIC_DEST_CPUS_MASK ((1u << XAPIC_DEST_CPUS_SHIFT) - 1)
#define XAPIC_DEST_CLUSTER_MASK (XAPIC_DEST_CPUS_MASK << XAPIC_DEST_CPUS_SHIFT)
#define APIC_CLUSTER(apicid) ((apicid) & XAPIC_DEST_CLUSTER_MASK)
#define APIC_CLUSTERID(apicid) (APIC_CLUSTER(apicid) >> XAPIC_DEST_CPUS_SHIFT)
/*
* cluster: high 4 bits
* cpu: low 4 bits
*/
#define APIC_CPUID(apicid) ((apicid) & XAPIC_DEST_CPUS_MASK)
#define NUM_APIC_CLUSTERS ((BAD_APICID + 1) >> XAPIC_DEST_CPUS_SHIFT)
/*
* Basic functions accessing LAPIC
*
* 类似 pci_read_config_dword
*/
static __inline void apic_write(unsigned long reg, unsigned int v)
{
*((volatile unsigned int *)(APIC_BASE+reg)) = v;
}
static __inline unsigned int apic_read(unsigned long reg)
{
return *((volatile unsigned int *)(APIC_BASE+reg));
}
/*
* Basic functions 的具体应用
*/
static inline void ack_APIC_irq(void)
{
/*
* ack_APIC_irq() actually gets compiled as a single instruction:
* - a single rmw on Pentium/82489DX
* - a single write on P6+ cores (CONFIG_X86_GOOD_APIC)
* ... yummie.
*/
/* Docs say use 0 for future compatibility */
apic_write(APIC_EOI, 0);
}
/*
有了basic，就可以摆弄寄存器了，
八哥坚持认为，摆弄寄存器是三流代码，照着manul添就是了，
不如CFQ in block, CBQ in QoS自由和浪漫，
不过，摆弄好了，也是功夫。
*/
extern int get_maxlvt (void);
extern void clear_local_APIC (void);
extern void connect_bsp_APIC (void);
extern void disconnect_bsp_APIC (int virt_wire_setup);
extern void disable_local_APIC (void);
extern int verify_local_APIC (void);
extern void cache_APIC_registers (void);
extern void sync_Arb_IDs (void);
extern void init_bsp_APIC (void);
extern void setup_local_APIC (void);
extern void init_apic_mappings (void);
extern void smp_local_timer_interrupt (void);
extern void setup_boot_APIC_clock (void);
extern void setup_secondary_APIC_clock (void);
extern int APIC_init_uniprocessor (void);
extern void disable_APIC_timer(void);
extern void enable_APIC_timer(void);
extern void setup_apic_routing(void);
extern void setup_APIC_extened_lvt(unsigned char lvt_off, unsigned char vector,
unsigned char msg_type, unsigned char mask);
#define K8_APIC_EXT_LVT_BASE 0x500
#define K8_APIC_EXT_INT_MSG_FIX 0x0
#define K8_APIC_EXT_INT_MSG_SMI 0x2
#define K8_APIC_EXT_INT_MSG_NMI 0x4
#define K8_APIC_EXT_INT_MSG_EXT 0x7
#define K8_APIC_EXT_LVT_ENTRY_THRESHOLD 0
void smp_send_timer_broadcast_ipi(void);
void switch_APIC_timer_to_ipi(void *cpumask);
void switch_ipi_to_APIC_timer(void *cpumask);
#define ARCH_APICTIMER_STOPS_ON_C3 1
extern unsigned boot_cpu_id;
extern int local_apic_timer_c2_ok;

复制代码

/* ===== in x86_64/kernel/apic.c ====== */
static __init int setup_disableapic(char *str)
{
disable_apic = 1;
/*
* P not only in APIC, but also
*/
clear_bit(X86_FEATURE_APIC, boot_cpu_data.x86_capability);
return 0;
}
early_param("disableapic", setup_disableapic);
/*
* This initializes the IO-APIC and APIC hardware if this is
* a UP kernel.
*/
int __init APIC_init_uniprocessor(void)
{
if (disable_apic) {
printk(KERN_INFO "Apic disabled\n");
return -1;
}
if (!cpu_has_apic) {
disable_apic = 1;
printk(KERN_INFO "Apic disabled by BIOS\n");
return -1;
}
verify_local_APIC();
phys_cpu_present_map = physid_mask_of_physid(boot_cpu_id);
/*
* 1, what cpu is in APIC space
*/
apic_write(APIC_ID, SET_APIC_ID(boot_cpu_id));
/*
* 2, LAPIC first
*/
setup_local_APIC();
if (smp_found_config
&& !skip_ioapic_setup
&& nr_ioapics) {
/*
* 3, then IO APIC if at least smp_found_config
* why??
* maybe IRT unecessary
*/
setup_IO_APIC();
} else
nr_ioapics = 0;
/*
* 4, and LAPIC clock
*/
setup_boot_APIC_clock();
/*
* 5, finally NMI
*/
check_nmi_watchdog();
return 0;
}
asmlinkage void smp_error_interrupt(void)
{
unsigned int v, v1;
exit_idle();
irq_enter();
/*
First tickle the hardware,
only then report what went on.
-- REW
*/
v = apic_read(APIC_ESR);
apic_write(APIC_ESR, 0);
v1 = apic_read(APIC_ESR);
ack_APIC_irq();
/*
* and the order is important, why not???
v = apic_read(APIC_ESR);
apic_write(APIC_ESR, 0);
ack_APIC_irq();
v1 = apic_read(APIC_ESR);
*/
atomic_inc(&irq_err_count);
/* Here is what the APIC error bits mean:
0: Send CS error
1: Receive CS error
2: Send accept error
3: Receive accept error
4: Reserved
5: Send illegal vector
6: Received illegal vector
7: Illegal register address
*/
printk (KERN_DEBUG "APIC error on CPU%d: %02x(%02x)\n",
smp_processor_id(), v , v1);
irq_exit();
}
asmlinkage void smp_spurious_interrupt (void)
{
unsigned int v;
exit_idle();
irq_enter();
/*
* Check if this really is a spurious interrupt and ACK it.
* if it is a vectored one. Just in case...
* Spurious interrupts should not be ACKed.
*/
v = apic_read(APIC_ISR + ((SPURIOUS_APIC_VECTOR & ~0x1f) >> 1));
if (v & (1 << (SPURIOUS_APIC_VECTOR & 0x1f)))
ack_APIC_irq();
/* ack should be ASAP,
* and tell user innomarl occured,
*
* 八哥遇见e100-82559中断无人处理的情况，on Intel-5110,
* 系统将其关闭。
*/
{
static unsigned long last_warning;
static unsigned long skipped;
/* see sw-dev-man vol 3, chapter 7.4.13.5 */
/// if (time_before(last_warning+30*HZ, jiffies)) {
if (time_before(jiffies, last_warning +30*HZ)) {
printk(KERN_INFO
"spurious APIC interrupt on CPU#%d, %ld skipped.\n",
smp_processor_id(), skipped);
last_warning = jiffies;
skipped = 0;
} else {
skipped++;
}
}
irq_exit();
}
/*
* LAPIC包含一个内部时钟 and operation
*/
void enable_APIC_timer (void)
{
/*
* 多数情况的应用是logic cpu number
*/
int cpu = smp_processor_id();
if (using_apic_timer &&
!cpu_isset(cpu, timer_interrupt_broadcast_ipi_mask)) {
unsigned long v;
v = apic_read(APIC_LVTT);
apic_write(APIC_LVTT, v & ~APIC_LVT_MASKED);
}
}
/*
* goto read manul by AMD
*/
void setup_APIC_extened_lvt(unsigned char lvt_off, unsigned char vector,
unsigned char msg_type, unsigned char mask)
{
unsigned long reg = (lvt_off << 4) + K8_APIC_EXT_LVT_BASE;
unsigned int v = (mask << 16) | (msg_type << 8) | vector;
apic_write(reg, v);
}
void smp_send_timer_broadcast_ipi(void)
{
int cpu = smp_processor_id();
cpumask_t mask;
cpus_and(mask, cpu_online_map,
timer_interrupt_broadcast_ipi_mask);
if (cpu_isset(cpu, mask)) {
cpu_clear(cpu, mask);
add_pda(apic_timer_irqs, 1);
smp_local_timer_interrupt();
}
/*
* 请 cpus in mask do IRQ represented by LOCAL_TIMER_VECTOR,
* cpu 不懂IRQ，but vector
*
* 这样的应用方式大有意思。
*/
if (!cpus_empty(mask))
send_IPI_mask(mask, LOCAL_TIMER_VECTOR);
}
/*
* 编程APIC，启用timer
*/
void enable_APIC_timer (void)
{
int cpu = smp_processor_id();
if (using_apic_timer &&
!cpu_isset(cpu, timer_interrupt_broadcast_ipi_mask)) {
unsigned long v;
v = apic_read(APIC_LVTT);
apic_write(APIC_LVTT, v & ~APIC_LVT_MASKED);
}
}
static int __init calibrate_APIC_clock(void)
{
unsigned apic, apic_start;
unsigned long tsc, tsc_start;
int result;
/*
* Put whatever arbitrary (but long enough) timeout
* value into the APIC clock, we just want to get the
* counter running for calibration.
*/
__setup_APIC_LVTT(4000000000);
apic_start = apic_read(APIC_TMCCT);
#ifdef CONFIG_X86_PM_TIMER
if (apic_calibrate_pmtmr && pmtmr_ioport) {
pmtimer_wait(5000); /* 5ms wait */
apic = apic_read(APIC_TMCCT);
result = (apic_start - apic) * 1000L / 5;
} else
#endif
{
/*
* tsc, timestamp counter,
* 这个准一些，亚纳秒级的精度。
*/
rdtscll(tsc_start);
do {
apic = apic_read(APIC_TMCCT);
rdtscll(tsc);
} while ((tsc - tsc_start) < TICK_COUNT &&
(apic_start - apic) < TICK_COUNT);
/* 得到微秒级的结果 */
result = (apic_start - apic) * 1000L * tsc_khz /
(tsc - tsc_start);
}
printk("result %d\n", result);
printk(KERN_INFO "Detected %d.%03d MHz APIC timer.\n",
result / 1000 / 1000, result / 1000 % 1000);
return result * APIC_DIVISOR / HZ;
}
/*
* This function sets up the local APIC timer,
* with a timeout of 'clocks' APIC bus clock.
*/
static void __setup_APIC_LVTT(unsigned int clocks)
{
unsigned int lvtt_value, tmp_value;
int cpu = smp_processor_id();
lvtt_value = APIC_LVT_TIMER_PERIODIC | LOCAL_TIMER_VECTOR;
if (cpu_isset(cpu, timer_interrupt_broadcast_ipi_mask))
lvtt_value |= APIC_LVT_MASKED;
apic_write(APIC_LVTT, lvtt_value);
/*
* Divide PICLK by 16
* 32, 64...1024 未必不可，不过没试过。
* 看看如何影响 Ingo Molnar的HPET
*/
tmp_value = apic_read(APIC_TDCR);
apic_write(APIC_TDCR,
(tmp_value & ~(APIC_TDR_DIV_1 | APIC_TDR_DIV_TMBASE))
| APIC_TDR_DIV_16);
apic_write(APIC_TMICT, clocks/APIC_DIVISOR);
}
void __init init_apic_mappings(void)
{
unsigned long apic_phys;
/*
* If no local APIC can be found then set up a fake all
* zeroes page to simulate the local APIC and another
* one for the IO-APIC.
*/
if (!smp_found_config && detect_init_APIC()) {
apic_phys = (unsigned long) alloc_bootmem_pages(PAGE_SIZE);
apic_phys = __pa(apic_phys);
} else /*
* 当然是硬件的,
* smp_found_config的由来，下回再说。
*/
apic_phys = mp_lapic_addr;
set_fixmap_nocache(FIX_APIC_BASE, apic_phys);
apic_mapped = 1;
apic_printk(APIC_VERBOSE,"mapped APIC to %16lx (%16lx)\n",
APIC_BASE, apic_phys);
/* Put local APIC into the resource map. */
lapic_resource.start = apic_phys;
lapic_resource.end = lapic_resource.start + PAGE_SIZE - 1;
insert_resource(&iomem_resource, &lapic_resource);
/*
* Fetch the APIC ID of the BSP in case we have a
* default configuration (or the MP table is broken).
*
* 对应smp_processor_id
*/
boot_cpu_id = GET_APIC_ID(apic_read(APIC_ID));
{
unsigned long ioapic_phys, idx = FIX_IO_APIC_BASE_0;
int i;
struct resource *ioapic_res;
ioapic_res = ioapic_setup_resources();
for (i = 0; i < nr_ioapics; i++) {
if (smp_found_config) {
ioapic_phys = mp_ioapics[i].mpc_apicaddr;
} else {
ioapic_phys = (unsigned long) alloc_bootmem_pages(PAGE_SIZE);
ioapic_phys = __pa(ioapic_phys);
}
set_fixmap_nocache(idx, ioapic_phys);
apic_printk(APIC_VERBOSE,
"mapped IOAPIC to %016lx (%016lx)\n",
__fix_to_virt(idx), ioapic_phys);
idx++;
if (ioapic_res != NULL) {
ioapic_res->start = ioapic_phys;
ioapic_res->end = ioapic_phys + (4 * 1024) - 1;
ioapic_res++;
}
}
}
}
static int lapic_suspend(struct sys_device *dev, pm_message_t state);
/*
* 变化真快，LAPIC也睡觉，
* 还是请球王alb讲讲ACPI
*/
static int lapic_resume(struct sys_device *dev)
void __cpuinit setup_local_APIC (void)
{
unsigned int value, maxlvt;
int i, j;
value = apic_read(APIC_LVR);
BUILD_BUG_ON((SPURIOUS_APIC_VECTOR & 0x0f) != 0x0f);
/*
* Double-check whether this APIC is really registered.
* This is meaningless in clustered apic mode, so we skip it.
*/
if (!apic_id_registered())
BUG();
/*
* Intel recommends to set DFR, LDR and TPR before enabling
* an APIC. See e.g. "AP-388 82489DX User's Manual" (Intel
* document number 292116). So here it goes...
*/
init_apic_ldr();
/*
* Set Task Priority to 'accept all'.
* We never change this later on.
*
* 其一，linux 处理LAPIC与IOAPIC的关系如此简单，
* 这是主要关系
*/
value = apic_read(APIC_TASKPRI);
value &= ~APIC_TPRI_MASK;
apic_write(APIC_TASKPRI, value);
/*
* After a crash, we no longer service the interrupts and a pending
* interrupt from previous kernel might still have ISR bit set.
*
* Most probably by now CPU has serviced that pending interrupt and
* it might not have done the ack_APIC_irq() because it thought,
* interrupt came from i8259 as ExtInt. LAPIC did not get EOI so it
* does not clear the ISR bit and cpu thinks it has already serivced
* the interrupt. Hence a vector might get locked. It was noticed
* for timer irq (vector 0x31). Issue an extra EOI to clear ISR.
*/
for (i = APIC_ISR_NR - 1; i >= 0; i--) {
value = apic_read(APIC_ISR + i*0x10);
for (j = 31; j >= 0; j--) {
if (value & (1<<j))
ack_APIC_irq();
}
}
/*
* Now that we are all set up, enable the APIC
*/
value = apic_read(APIC_SPIV);
value &= ~APIC_VECTOR_MASK;
/*
* Enable APIC
*/
value |= APIC_SPIV_APIC_ENABLED;
/* We always use processor focus */
/*
* Set spurious IRQ vector
*/
value |= SPURIOUS_APIC_VECTOR;
apic_write(APIC_SPIV, value);
/*
* Set up LVT0, LVT1:
*
* set up through-local-APIC on the BP's LINT0. This is not
* strictly necessary in pure symmetric-IO mode, but sometimes
* we delegate interrupts to the 8259A.
*/
/*
* TODO: set up through-local-APIC from through-I/O-APIC? --macro
*/
value = apic_read(APIC_LVT0) & APIC_LVT_MASKED;
if (!smp_processor_id() && !value) {
value = APIC_DM_EXTINT;
apic_printk(APIC_VERBOSE, "enabled ExtINT on CPU#%d\n", smp_processor_id());
} else {
value = APIC_DM_EXTINT | APIC_LVT_MASKED;
apic_printk(APIC_VERBOSE, "masked ExtINT on CPU#%d\n", smp_processor_id());
}
apic_write(APIC_LVT0, value);
/*
* only the BP should see the LINT1 NMI signal, obviously.
*/
if (!smp_processor_id())
value = APIC_DM_NMI;
else
value = APIC_DM_NMI | APIC_LVT_MASKED;
apic_write(APIC_LVT1, value);
{
unsigned oldvalue;
maxlvt = get_maxlvt();
oldvalue = apic_read(APIC_ESR);
value = ERROR_APIC_VECTOR; // enables sending errors
apic_write(APIC_LVTERR, value);
/*
* spec says clear errors after enabling vector.
*/
if (maxlvt > 3)
apic_write(APIC_ESR, 0);
value = apic_read(APIC_ESR);
if (value != oldvalue)
apic_printk(APIC_VERBOSE,
"ESR value after enabling vector: %08x, after %08x\n",
oldvalue, value);
}
nmi_watchdog_default();
setup_apic_nmi_watchdog(NULL);
apic_pm_activate();
}
void __init init_bsp_APIC(void)
{
unsigned int value;
/*
* Don't do the setup now if we have a SMP BIOS as the
* through-I/O-APIC virtual wire mode might be active.
*/
if (smp_found_config || !cpu_has_apic)
return;
value = apic_read(APIC_LVR);
/*
* Do not trust the local APIC being empty at bootup.
*/
clear_local_APIC();
/*
* Enable APIC.
*/
value = apic_read(APIC_SPIV);
value &= ~APIC_VECTOR_MASK;
value |= APIC_SPIV_APIC_ENABLED;
/*
* 其二，BSP不用FOCUS
*/
value |= APIC_SPIV_FOCUS_DISABLED;
value |= SPURIOUS_APIC_VECTOR;
apic_write(APIC_SPIV, value);
/*
* Set up the virtual wire mode.
*/
apic_write(APIC_LVT0, APIC_DM_EXTINT);
value = APIC_DM_NMI;
apic_write(APIC_LVT1, value);
}
void __init sync_Arb_IDs(void)
{
/* Unsupported on P4 - see Intel Dev. Manual Vol. 3, Ch. 8.6.1 */
unsigned int ver = GET_APIC_VERSION(apic_read(APIC_LVR));
/* P4 or higher
* Intel 关于SMP的1.4版本
*/
if (ver >= 0x14)
return;
/*
* Wait for idle.
*/
apic_wait_icr_idle();
apic_printk(APIC_DEBUG, "Synchronizing Arb IDs.\n");
/*
* 其三，仲裁机制的使用
*/
apic_write(APIC_ICR, APIC_DEST_ALLINC |
APIC_INT_LEVELTRIG
| APIC_DM_INIT);
}

复制代码

static int modern_apic(void)
{
/* AMD systems use old APIC versions, so check the CPU */
if (boot_cpu_data.x86_vendor == X86_VENDOR_AMD &&
boot_cpu_data.x86 >= 0xf)
return 1;
/*
* linux is able to combine specifications by
* both Intel and AMD
*/
return lapic_get_version() >= 0x14;
}
int get_physical_broadcast(void)
{
/*
* v1.1 specifies 16 LAPIC
* v1.4 specifies 2566 LAPIC
*/
return modern_apic() ? 0xff : 0xf;
}
/* ===== end of LAPIC =====
summary:
1, two versions 1.1 and 1.4
2, the key of LAPIC is P from software point
3, programing lapic timer
4, programing lapic LINT0/1
5, programing lapic IRQ DM, delivery model

复制代码

IOAPIC[IRQ]
===========
IOAPIC比LAPIC麻烦些，有几种版本，
1，PIC，2个8259A
2，MPS，multi pentium standar
3，MADT，multi APIC description table
现在流行MADT，由BIOS提供。
part—1，basic def and operation
int nr_ioapic_registers[MAX_IO_APICS];
/*
* Rough estimation of how many shared IRQs there are, can
* be changed anytime.
*/
#define MAX_PLUS_SHARED_IRQS NR_IRQS
#define PIN_MAP_SIZE (MAX_PLUS_SHARED_IRQS + NR_IRQS)
/*
* This is performance-critical, we want to do it O(1)
*
* the indexing order of this array favors 1:1 mappings
* between pins and IRQs.
*/
static struct irq_pin_list
{
int apic,
pin,
next;
} irq_2_pin[PIN_MAP_SIZE];
struct io_apic
{
unsigned int index; /* reg indx */
unsigned int unused[3];
unsigned int data; /* reg value */
};
/*
in asm/io_apic.h
the chip is structured by linux as
IO_APIC_reg_0x + struct IO_APIC_route_entry
and that is all ;)
*/
union entry_union
{
/*
* or simply just a 64-bit number :/
*
* and currently engineers to play chip
* are strongly demanded, specially in CNY,
* not by linux??
*/
struct { u32 w1, w2; } ;
struct IO_APIC_route_entry entry;
};
static struct io_apic __iomem * __attribute_const__ io_apic_base (int idx)
{
return (void __iomem *) __fix_to_virt(FIX_IO_APIC_BASE_0 + idx)
+ (mp_ioapics[idx].mpc_apicaddr & ~PAGE_MASK);
/*
* mp_ioapics[],暂且认为是来自MADT
*/
}
static inline unsigned int io_apic_read (unsigned int apic, unsigned int reg)
{
struct io_apic __iomem *io_apic = io_apic_base(apic);
writel(reg, &io_apic->index);
return readl(&io_apic->data);
}
static inline void io_apic_write(unsigned int apic,
unsigned int reg, unsigned int value)
{
struct io_apic __iomem *io_apic = io_apic_base(apic);
writel(reg, &io_apic->index);
writel(value, &io_apic->data);
}

复制代码

part-2，IRT entry programming
static struct IO_APIC_route_entry ioapic_read_entry(int apic, int pin);
/*
* basic IRTE read/write, indexed by pin,
* but how is mapped to irq, then to vector??
*/
static void ioapic_write_entry (int apic, int pin,
struct IO_APIC_route_entry e);
/* shutup IRQ mapped by pin */
static void ioapic_mask_entry (int apic, int pin);
/*
* IRQ<-->pin mapping table is irq_2_pin[]
*
* but where irq come from??
*/
static void add_pin_to_irq (unsigned int irq, int apic, int pin)
{
static int first_free_entry = NR_IRQS;
struct irq_pin_list *entry = irq_2_pin + irq;
while (entry->next)
entry = irq_2_pin + entry->next;
if (entry->pin != -1) {
/*
* in case IRQ is shared
*/
entry->next = first_free_entry;
entry = irq_2_pin + entry->next;
if (++first_free_entry >= PIN_MAP_SIZE)
panic("io_apic.c: whoops");
}
entry->apic = apic;
entry->pin = pin;
}
/*
* Reroute an IRQ to a different pin
*
* or, cfg pin to use IRQ
*/
static void __init replace_pin_at_irq(unsigned int irq,
int oldapic, int oldpin,
int newapic, int newpin);
/*
* core programing method,
* first read, then write.
*/
static void __modify_IO_APIC_irq (unsigned int irq,
unsigned long enable,
unsigned long disable)
static void clear_IO_APIC_pin (unsigned int apic, unsigned int pin)
{
/*
* in chip of ioapic, pin is represented by route entry
*/
struct IO_APIC_route_entry entry;
/* Check delivery_mode to be sure we're not clearing an SMI pin */
entry = ioapic_read_entry(apic, pin);
if (entry.delivery_mode == dest_SMI)
return;
/*
* Disable it in the IO-APIC irq-routing table:
*/
ioapic_mask_entry(apic, pin);
}

复制代码

part-3 irq affinity/balance
非常高兴，关于balance在CU已经看见思一克漂亮的工作，
这里八哥就不费心了。

复制代码

part-4 麻烦来了，MADT/MPS
/*
* Find the IRQ entry number of a certain pin
*/
static int find_irq_entry (int apic, int pin, int type)
{
int i;
/*
* bonding of irq and pin is pre-defined?!
*/
for (i = 0; i < mp_irq_entries; i++) {
if (mp_irqs[i].mpc_irqtype == type &&
(mp_irqs[i].mpc_dstapic == mp_ioapics[apic].mpc_apicid ||
mp_irqs[i].mpc_dstapic == MP_APIC_ALL) &&
mp_irqs[i].mpc_dstirq == pin)
return i;
}
return -1;
}
/*
* seems it is impossible to make IRQ unshared, if
* two pci devices cfged shared in mp_irqs[]??
* and it is appreciated in practical usage where
* unshared IRQ preferred.
*/
static int __init find_pci_irq_pin (int irq, int type)
{
int i;
for (i = 0; i < mp_irq_entries; i++) {
int lbus;
lbus = mp_irqs[i].mpc_srcbus;
if (mp_bus_id_to_type[lbus] == MP_BUS_PCI
&& mp_irqs[i].mpc_irqtype == type
&& mp_irqs[i].mpc_srcbusirq == irq) /* defined in this way */
return mp_irqs[i].mpc_dstirq; /* and its pin */
}
return -1;
}
/*
* Find a specific PCI IRQ entry
*
*********************************************
* Not an __init, possibly needed by modules *
*********************************************
*
* linux从不决人后路，如果Solaris敢放马开放，
* linux充分吸收后，就没有吸引用户的必要了，请鳖揭开面纱。
*/
int IO_APIC_get_PCI_irq_vector (int bus, int slot, int pin)
{
int apic, i, best_guess = -1;
apic_printk(APIC_DEBUG, "querying PCI -> IRQ mapping bus%d, "
"slot%d, pin%d\n", bus, slot, pin);
if (mp_bus_id_to_pci_bus[bus] == -1) {
printk(KERN_WARNING
"PCI BIOS passed nonexistent PCI bus%d!\n", bus);
return -1;
}
for (i = 0; i < mp_irq_entries; i++) {
int lbus = mp_irqs[i].mpc_srcbus;
for (apic = 0; apic < nr_ioapics; apic++) {
/*
* determine IRQ controler
*/
if (mp_irqs[i].mpc_dstapic == mp_ioapics[apic].mpc_apicid
|| mp_irqs[i].mpc_dstapic == MP_APIC_ALL)
break;
}
if (mp_bus_id_to_type[lbus] == MP_BUS_PCI
&& !mp_irqs[i].mpc_irqtype /* need confirm */
&& bus == lbus /* both bus and slot match */
&& slot == (mp_irqs[i].mpc_srcbusirq >> 2) & 0x1f) {
int irq;
irq = pin_2_irq(i, apic, mp_irqs[i].mpc_dstirq);
if (!(apic || IO_APIC_IRQ(irq)))
continue;
/*
* and pin match
*/
if (pin == (mp_irqs[i].mpc_srcbusirq & 3))
return irq;
/*
* Use the first all-but-pin matching entry as a
* best-guess fuzzy result for broken mptables.
*/
if (best_guess < 0)
best_guess = irq;
}
}
return best_guess;
}
/*
* irq of pci_bus:slot.dev is determined in IOAPIC space
* 1, to which controler connected and pin?
* 2, irq = controler_nr * nr_irte + pin
* limited currently by
* 256 vector per cpu
* 128 controler
* 24 irte per controler
*
* irt<-->LAPIC mapping can also be programmed,
* goto see set_ioapic_affinity_irq(irq, TARGET_CPUS) and
* balanced_irq_init()
*
* the major purpose of MADT maybe tell OS controler and pin,
* irq can be re-cfged.
* no problem, ok.
*/
static int pin_2_irq (int idx, int apic, int pin)
{
int irq, i;
int bus = mp_irqs[idx].mpc_srcbus;
/*
* Debugging check, we are in big trouble if this message pops up!
*/
if (mp_irqs[idx].mpc_dstirq != pin)
printk(KERN_ERR "broken BIOS or MPTABLE parser in pin_2_irq, ayiee!!\n");
switch (mp_bus_id_to_type[bus])
{
case MP_BUS_ISA: /* ISA pin */
case MP_BUS_EISA:
case MP_BUS_MCA:
{
irq = mp_irqs[idx].mpc_srcbusirq;
break;
}
case MP_BUS_PCI: /* PCI pin */
{
/*
* PCI IRQs are mapped in order
*/
i = irq = 0;
while (i < apic)
irq += nr_ioapic_registers[i++];
irq += pin;
/*
* For MPS mode, so far only needed by ES7000 platform
*/
if (ioapic_renumber_irq)
irq = ioapic_renumber_irq(apic, irq);
break;
}
default:
{
printk(KERN_ERR "unknown bus type %d in pin_2_irq\n",bus);
irq = 0;
break;
}
}
/*
* PCI IRQ command line redirection.
* Yes, limits are hardcoded.
*/
if (pin >= 16 && pin <= 23) {
if (pirq_entries[pin -16] != -1) {
if (!pirq_entries[pin -16]) {
apic_printk(APIC_VERBOSE, KERN_DEBUG
"disabling PIRQ%d\n", pin -16);
} else {
irq = pirq_entries[pin -16];
apic_printk(APIC_VERBOSE, KERN_DEBUG
"using PIRQ%d -> IRQ %d\n", pin -16, irq);
}
}
}
return irq;
}

复制代码

part-5 IRQ attr: trigger/polarity
/*
* 不仅变化快，还很复杂，
* trigger: edge/level
* polarity: high/low
*/
/*
* check irq is level or edge
*/
static inline int IO_APIC_irq_trigger (int irq)
{
int apic, idx, pin;
for (apic = 0; apic < nr_ioapics; apic++) {
for (pin = 0; pin < nr_ioapic_registers[apic]; pin++) {
idx = find_irq_entry(apic, pin, mp_INT);
if (idx != -1
&& irq == pin_2_irq(idx, apic, pin))
return irq_trigger(idx);
}
}
/*
* nonexistent IRQs are edge default
*/
return 0;
}

复制代码

part-6 vector[IRQ]
/*
* irq_vectors is indexed by the sum of all RTEs in all I/O APICs
*/
static u8 irq_vector[NR_IRQ_VECTORS] __read_mostly = { FIRST_DEVICE_VECTOR , 0 };
static int __assign_irq_vector (int irq)
{
static int current_vector = FIRST_DEVICE_VECTOR;
static int current_offset = 0;
int vector, offset, i;
BUG_ON((unsigned)irq >= NR_IRQ_VECTORS);
if (irq_vector[irq] > 0) /* shared irq */
return irq_vector[irq];
vector = current_vector;
offset = current_offset;
next:
vector += 8;
if (vector >= FIRST_SYSTEM_VECTOR) {
offset = (offset + 1) % 8;
/*
* the vector of pci-irq has to
* be larger than FIRST_DEVICE_VECTOR,
* imposed by Intel
*/
vector = FIRST_DEVICE_VECTOR + offset;
}
if (vector == current_vector)
return -ENOSPC;
if (vector == SYSCALL_VECTOR)
goto next;
for (i = 0; i < NR_IRQ_VECTORS; i++)
if (irq_vector[i] == vector)
goto next;
current_vector = vector;
current_offset = offset;
irq_vector[irq] = vector;
return vector;
}
static struct irq_chip ioapic_chip;
#define IOAPIC_AUTO -1
#define IOAPIC_EDGE 0
#define IOAPIC_LEVEL 1
static void ioapic_register_intr (int irq, int vector, unsigned long trigger)
{
if ((trigger == IOAPIC_AUTO && IO_APIC_irq_trigger(irq))
|| trigger == IOAPIC_LEVEL)
set_irq_chip_and_handler_name(irq, &ioapic_chip,
handle_fasteoi_irq, "fasteoi");
else
set_irq_chip_and_handler_name(irq, &ioapic_chip,
handle_edge_irq, "edge");
set_intr_gate(vector, interrupt[irq]);
}
/* and put all together through
* __ioapic_write_entry(apic, pin, entry);
*/
static void __init setup_IO_APIC_irqs (void);
/*
* finally setup
* struct irq_chip msi_chip, lapic_chip and ioapic_chip
* for use by struct irq_desc,
* the nut of linux abstract core of IRQ subsystem
*/
[homework]
1, howto make pci-dev irqs unshared??
2, is IT from independent thought??
[/homework]

复制代码

#ifdef CONFIG_SMP
/*
* linux-2.6.22.5/arch/i386/kernel/io_apic.c
* 2007-12-16 10:18
* ￥1
*/
static void set_msi_irq_affinity (unsigned int irq, cpumask_t mask)
{
struct msi_msg msg;
unsigned int dest;
cpumask_t tmp;
int vector;
cpus_and(tmp, mask, cpu_online_map);
if (cpus_empty(tmp))
tmp = TARGET_CPUS;
/*
* though tmp checked, but not used anymore.
* the following `mask' should be tmp
*
* mask = tmp;
*/
vector = assign_irq_vector(irq);
if (vector < 0)
return;
dest = cpu_mask_to_apicid(mask);
read_msi_msg(irq, &msg);
msg.data &= ~MSI_DATA_VECTOR_MASK;
msg.data |= MSI_DATA_VECTOR(vector);
msg.address_lo &= ~MSI_ADDR_DEST_ID_MASK;
msg.address_lo |= MSI_ADDR_DEST_ID(dest);
write_msi_msg(irq, &msg);
irq_desc[irq].affinity = mask;
}
#endif

复制代码

/* linux-2.6.22.5/arch/x86_64/kernel/mpparse.c
* 2007-12-16 19:20
* ￥1
*/
static void __init MP_ioapic_info (struct mpc_config_ioapic *m)
{
if (!(m->mpc_flags & MPC_APIC_USABLE))
return;
printk("I/O APIC #%d at 0x%X.\n",
m->mpc_apicid, m->mpc_apicaddr);
if (bad_ioapic(m->mpc_apicaddr))
return;
/*
printk("I/O APIC #%d at 0x%X",
m->mpc_apicid, m->mpc_apicaddr);
if (bad_ioapic(m->mpc_apicaddr)) {
printk(" bad\n");
return;
} else
printk("\n");
*/
mp_ioapics[nr_ioapics] = *m;
nr_ioapics++;
}

复制代码

/* linux-2.6.22.5/include/linux/skbuff.h
* 2007-12-19 20:52
* ￥1
*/
static inline int pskb_may_pull(struct sk_buff *skb, unsigned int len)
{
if (likely(len <= skb_headlen(skb))) {
/*
* howto sure skb->data += len not overflow ?
*/
return 1;
}
if (unlikely(len > skb->len))
return 0;
return __pskb_pull_tail(skb, len-skb_headlen(skb)) != NULL;
}

复制代码

/*
linux-2.6.22.5/kernel/workqueue.c
2007-12-22 9:19
*/
struct workqueue_struct *__create_workqueue(const char *name,
int singlethread, int freezeable)
{
struct workqueue_struct *wq;
struct cpu_workqueue_struct *cwq;
int err = 0, cpu;
wq = kzalloc(sizeof(*wq), GFP_KERNEL);
if (!wq)
return NULL;
wq->cpu_wq = alloc_percpu(struct cpu_workqueue_struct);
if (!wq->cpu_wq) {
kfree(wq);
return NULL;
}
wq->name = name;
wq->singlethread = singlethread;
wq->freezeable = freezeable;
INIT_LIST_HEAD(&wq->list);
if (singlethread) {
cwq = init_cpu_workqueue(wq, singlethread_cpu);
err = create_workqueue_thread(cwq, singlethread_cpu);
start_workqueue_thread(cwq, -1);
} else {
mutex_lock(&workqueue_mutex);
list_add(&wq->list, &workqueues);
for_each_possible_cpu(cpu) {
cwq = init_cpu_workqueue(wq, cpu);
/*
if (!cpu_online(cpu))
continue;
if (err)
break;
*/
if (err || !cpu_online(cpu))
continue;
err = create_workqueue_thread(cwq, cpu);
start_workqueue_thread(cwq, cpu);
}
mutex_unlock(&workqueue_mutex);
}
if (err) {
destroy_workqueue(wq);
wq = NULL;
}
return wq;
}

复制代码

/*
linux-2.6.22.5/net/netfilter/nf_conntrack_proto_tcp.c
2007-12-22 10:38
￥6
howto crash netfilter with TCP SYN packet, possible?
*/
static int tcp_error(struct sk_buff *skb,
unsigned int dataoff,
enum ip_conntrack_info *ctinfo,
int pf,
unsigned int hooknum)
{
struct tcphdr _tcph, *th;
unsigned int tcplen = skb->len - dataoff;
u_int8_t tcpflags;
/* Smaller that minimal TCP header? */
th = skb_header_pointer(skb, dataoff, sizeof(_tcph), &_tcph);
if (th == NULL) {
if (LOG_INVALID(IPPROTO_TCP))
nf_log_packet(pf, 0, skb, NULL, NULL, NULL,
"nf_ct_tcp: short packet ");
return -NF_ACCEPT;
}
/* Not whole TCP header or malformed packet */
if (th->doff*4 < sizeof(struct tcphdr)
|| tcplen < th->doff*4) {
[color=Red] /*
* 其一隐患;/
* TCP头长大于60字节是合法的 8-(:
*/
[/color] if (LOG_INVALID(IPPROTO_TCP))
nf_log_packet(pf, 0, skb, NULL, NULL, NULL,
"nf_ct_tcp: truncated/malformed packet ");
return -NF_ACCEPT;
}
/* Checksum invalid? Ignore.
* We skip checking packets on the outgoing path
* because the checksum is assumed to be correct.
*/
/* FIXME: Source route IP option packets --RR */
if (nf_conntrack_checksum &&
((pf == PF_INET && hooknum == NF_IP_PRE_ROUTING) ||
(pf == PF_INET6 && hooknum == NF_IP6_PRE_ROUTING)) &&
nf_checksum(skb, hooknum, dataoff, IPPROTO_TCP, pf)) {
if (LOG_INVALID(IPPROTO_TCP))
nf_log_packet(pf, 0, skb, NULL, NULL, NULL,
"nf_ct_tcp: bad TCP checksum ");
return -NF_ACCEPT;
}
/* Check TCP flags. */
tcpflags = (((u_int8_t *)th)[13] & ~(TH_ECE|TH_CWR|TH_PUSH));
if (!tcp_valid_flags[tcpflags]) {
if (LOG_INVALID(IPPROTO_TCP))
nf_log_packet(pf, 0, skb, NULL, NULL, NULL,
"nf_ct_tcp: invalid TCP flag combination ");
return -NF_ACCEPT;
}
return NF_ACCEPT;
}
static void tcp_options(const struct sk_buff *skb,
unsigned int dataoff,
struct tcphdr *tcph,
struct ip_ct_tcp_state *state)
{
unsigned char buff[(15 * 4) - sizeof(struct tcphdr)];
unsigned char *ptr;
int length = (tcph->doff*4) - sizeof(struct tcphdr);
/*
* length可以大于40;/
* but sizeof(buff) = 40
*/
if (!length)
return;
ptr = skb_header_pointer(skb, dataoff + sizeof(struct tcphdr),
length, buff);
[color=Red] /*
* 其二 buff可能overflow
*/
[/color] BUG_ON(ptr == NULL);
state->td_scale = state->flags = 0;
while (length > 0) {
int opcode = *ptr++;
int opsize;
switch (opcode) {
case TCPOPT_EOL:
return;
case TCPOPT_NOP: /* Ref: RFC 793 section 3.1 */
length--;
continue;
default:
opsize = *ptr++;
if (opsize < 2) /* "silly options" */
return;
if (opsize > length)
break; /* don't parse partial options */
if (opcode == TCPOPT_SACK_PERM
&& opsize == TCPOLEN_SACK_PERM) {
state->flags |= IP_CT_TCP_FLAG_SACK_PERM;
}
else if (opcode == TCPOPT_WINDOW
&& opsize == TCPOLEN_WINDOW) {
state->td_scale = *(u_int8_t *)ptr;
if (state->td_scale > 14) {
/* See RFC1323 */
state->td_scale = 14;
}
state->flags |= IP_CT_TCP_FLAG_WINDOW_SCALE;
}
ptr += opsize - 2;
length -= opsize;
}
}
}
static inline void * skb_header_pointer (const struct sk_buff *skb,
int offset, int len, void *buffer)
{ /* in <linux/skbuff.h> */
int hlen = skb_headlen(skb);
if (hlen - offset >= len)
return skb->data + offset;
[color=Red] /*
* 其三如果是大SYN包，使得skb_copy_bits被调用了，
* if (len > 40 bytes)
* buffer overflow;
*
* 但是，netfilter看到的包都是整合过的，
* 这样的机会几乎没有，要看ipfrag reasm的结果
*/
[/color] if (skb_copy_bits(skb, offset, buffer, len) < 0)
return NULL;
return buffer;
}
int skb_copy_bits(const struct sk_buff *skb, int offset, void *to, int len)
{
int i, copy;
int start = skb_headlen(skb);
if (offset > (int)skb->len - len)
goto fault;
/* Copy header. */
if ((copy = start - offset) > 0) {
if (copy > len)
copy = len;
/*
这里没有check len，
而是默认len <= sizeof(to)
*/
skb_copy_from_linear_data_offset(skb, offset, to, copy);
if ((len -= copy) == 0)
return 0;
offset += copy;
to += copy;
}
...
}
void * memcpy(void *dest, const void *src, size_t count)
{
/*
C版的memcpy in lib/string.c
memcpy没有检测overflow的义务;/
*/
char *tmp = dest;
const char *s = src;
while (count--)
*tmp++ = *s++;
return dest;
}
static struct sk_buff * ip_frag_reasm (struct ipq *qp, struct net_device *dev)
{ /* net/ipv4/ip_fragment.c */
struct iphdr *iph;
struct sk_buff *fp, *head = qp->fragments;
int len;
int ihlen;
ipq_kill(qp);
BUG_TRAP(head != NULL);
BUG_TRAP(FRAG_CB(head)->offset == 0);
/* Allocate a new buffer for the datagram. */
ihlen = ip_hdrlen(head);
len = ihlen + qp->len;
if (len > 65535)
goto out_oversize;
/* Head of list must not be cloned. */
if (skb_cloned(head) && pskb_expand_head(head, 0, 0, GFP_ATOMIC))
goto out_nomem;
/* If the first fragment is fragmented itself, we split
* it to two chunks: the first with data and paged part
* and the second, holding only fragments. */
if (skb_shinfo(head)->frag_list) {
struct sk_buff *clone;
int i, plen = 0;
if ((clone = alloc_skb(0, GFP_ATOMIC)) == NULL)
goto out_nomem;
clone->next = head->next;
head->next = clone;
skb_shinfo(clone)->frag_list = skb_shinfo(head)->frag_list;
skb_shinfo(head)->frag_list = NULL;
for (i=0; i<skb_shinfo(head)->nr_frags; i++)
plen += skb_shinfo(head)->frags[i].size;
clone->len = clone->data_len = head->data_len - plen;
head->data_len -= clone->len;
head->len -= clone->len;
clone->csum = 0;
clone->ip_summed = head->ip_summed;
atomic_add(clone->truesize, &ip_frag_mem);
}
skb_shinfo(head)->frag_list = head->next;
[color=Red] /*
* 其四 linux skb精巧的设计，可以方便地处理大包 &)
*
* 在这里没有实施linearize，性能可佳。
*/
[/color] skb_push(head, head->data - skb_network_header(head));
atomic_sub(head->truesize, &ip_frag_mem);
for (fp = head->next; fp; fp = fp->next) {
head->data_len += fp->len;
[color=Red] /*
* 由于没有linearize操作，
* 虽然总包长要求len < 65535 byte,
* 首包长确可以是
* 82byte = 20byte<IP> + 60byte<TCP> + 2byte<trash>
*
* 所以 tcp->doff*4 = 88byte,
* 将迫使skb_header_pointer调用skb_copy_bits，
* 结果导致40byte的buff overflow
*/
[/color] head->len += fp->len;
if (head->ip_summed != fp->ip_summed)
head->ip_summed = CHECKSUM_NONE;
else if (head->ip_summed == CHECKSUM_COMPLETE)
head->csum = csum_add(head->csum, fp->csum);
head->truesize += fp->truesize;
atomic_sub(fp->truesize, &ip_frag_mem);
}
head->next = NULL;
head->dev = dev;
head->tstamp = qp->stamp;
iph = ip_hdr(head);
iph->frag_off = 0;
iph->tot_len = htons(len);
IP_INC_STATS_BH(IPSTATS_MIB_REASMOKS);
qp->fragments = NULL;
return head;
out_nomem:
LIMIT_NETDEBUG(KERN_ERR "IP: queue_glue: no memory for gluing "
"queue %p\n", qp);
goto out_fail;
out_oversize:
if (net_ratelimit())
printk(KERN_INFO
"Oversized IP packet from %d.%d.%d.%d.\n",
NIPQUAD(qp->saddr));
out_fail:
IP_INC_STATS_BH(IPSTATS_MIB_REASMFAILS);
return NULL;
}

复制代码

struct tcphdr {
__be16 source;
__be16 dest;
__be32 seq;
__be32 ack_seq;
#if defined(__LITTLE_ENDIAN_BITFIELD)
__u16 res1:4,
doff:4, /* 正解 doff *4 <= 60, 逗你玩 */
fin:1,
syn:1,
rst:1,
psh:1,
ack:1,
urg:1,
ece:1,
cwr:1;
#elif defined(__BIG_ENDIAN_BITFIELD)
__u16 doff:4,
res1:4,
cwr:1,
ece:1,
urg:1,
ack:1,
psh:1,
rst:1,
syn:1,
fin:1;
#else
#error "Adjust your <asm/byteorder.h> defines"
#endif
__be16 window;
__sum16 check;
__be16 urg_ptr;
};

复制代码

/* 2007-12-22 20:47 */
static void tcp_options(const struct sk_buff *skb,
unsigned int dataoff,
struct tcphdr *tcph,
struct ip_ct_tcp_state *state)
{
unsigned char buff[(15 * 4) - sizeof(struct tcphdr)];
unsigned char *ptr;
int length = (tcph->doff*4) - sizeof(struct tcphdr);
/*
* sizeof(buff) = 40
* length 只能 <= 40 ;)
*/
if (!length)
return;
ptr = skb_header_pointer(skb, dataoff + sizeof(struct tcphdr),
length, buff);
/*108byte(20byte<IP> +
* 20byte<TCP> +
* 40byte<TCP opt> +
* 28byte<trash>)SYN 包拆成两个碎片:
* 第一个包：20byte<IP> + 20byte<TCP> + 24byte<TCP opt>
* and tcp->doff = 0xf
* 第二个包：20byte<IP> + 16byte<TCP opt> + 28byte<trash>
*
* 这样会迫使 ptr = buff ;/
* =========================
* 40byte<TCP opt>这样填充，使得：
* buff[0 ... 38] = TCPOPT_NOP ;
* buff[39] = 非 TCPOPT_NOP and TCPOPT_EOL
*/
BUG_ON(ptr == NULL);
state->td_scale = state->flags = 0;
while (length > 0) {
/*
* when length = 1, ptr = &buff[39], and
* while-loop progress...
*/
int opcode = *ptr++;
/*
* after opcode is read,
* ptr = &buff[40]
* still ok,
*/
int opsize;
switch (opcode) {
case TCPOPT_EOL:
return;
case TCPOPT_NOP: /* Ref: RFC 793 section 3.1 */
length--;
continue;
default:
/*
* but when opsize is reading,
* buff overflow :?/
*/
opsize = *ptr++;
if (opsize < 2) /* "silly options" */
return;
if (opsize > length)
break; /* don't parse partial options */
if (opcode == TCPOPT_SACK_PERM
&& opsize == TCPOLEN_SACK_PERM) {
state->flags |= IP_CT_TCP_FLAG_SACK_PERM;
}
else if (opcode == TCPOPT_WINDOW
&& opsize == TCPOLEN_WINDOW) {
state->td_scale = *(u_int8_t *)ptr;
if (state->td_scale > 14) {
/* See RFC1323 */
state->td_scale = 14;
}
state->flags |= IP_CT_TCP_FLAG_WINDOW_SCALE;
}
ptr += opsize - 2;
length -= opsize;
}
}
}

复制代码

/* Print out the private part of the conntrack. */
static int tcp_print_conntrack(struct seq_file *s,
const struct ip_conntrack *conntrack)
{
enum tcp_conntrack state;
read_lock_bh(&tcp_lock);
/* 这里 state 可能取到很多值 */
state = conntrack->proto.tcp.state;
read_unlock_bh(&tcp_lock);
/* 这里显示具体的 state */
return seq_printf(s, "%s ", tcp_conntrack_names[state]);
}

复制代码

static const char *tcp_conntrack_names[] = {
"NONE",
"SYN_SENT",
"SYN_RECV",
"ESTABLISHED",
"FIN_WAIT",
"CLOSE_WAIT",
"LAST_ACK",
"TIME_WAIT",
"CLOSE",
"LISTEN"
};

复制代码

/* This is exposed to userspace (ctnetlink) */
enum tcp_conntrack {
TCP_CONNTRACK_NONE,
TCP_CONNTRACK_SYN_SENT,
TCP_CONNTRACK_SYN_RECV,
TCP_CONNTRACK_ESTABLISHED,
TCP_CONNTRACK_FIN_WAIT,
TCP_CONNTRACK_CLOSE_WAIT,
TCP_CONNTRACK_LAST_ACK,
TCP_CONNTRACK_TIME_WAIT,
TCP_CONNTRACK_CLOSE,
TCP_CONNTRACK_LISTEN,
TCP_CONNTRACK_MAX, /* 这个没有出现在 tcp_conntrack_names 中 */
TCP_CONNTRACK_IGNORE /* 同上 */
};

复制代码

struct ip_ct_tcp
{
struct ip_ct_tcp_state seen[2]; /* connection parameters per direction */
u_int8_t state; /* state of the connection (enum tcp_conntrack) */
/* 这里取的可是 enum tcp_conntrack 的值啊？ */
/* For detecting stale connections */
u_int8_t last_dir; /* Direction of the last packet (enum ip_conntrack_dir) */
u_int8_t retrans; /* Number of retransmitted packets */
u_int8_t last_index; /* Index of the last packet */
u_int32_t last_seq; /* Last sequence number seen in dir */
u_int32_t last_ack; /* Last sequence number seen in opposite dir */
u_int32_t last_end; /* Last seq + len */
u_int16_t last_win; /* Last window advertisement seen in dir */
};

复制代码

#include <net/snmp.h>
#include <net/ip.h>
#include <net/protocol.h>
#include <net/route.h>
#include <net/xfrm.h>
#include <linux/skbuff.h>
#include <net/sock.h>
#include <net/arp.h>
#include <net/icmp.h>
/* why so much men? linux-2.6.22.5/net/ipv4/ip_output.c
#include <net/checksum.h> */
#include <net/inetpeer.h>
#include <net/checksum.h>
#include <linux/igmp.h>

复制代码

Hi, Jozsef
Though functions in nf_conntrack_proto_tcp.c never see fragmented packets,
the implementation of the function, ip_frag_reasm() in linux/net/ipv4/ip_fragment.c,
does not make sure that the skb seen in nf_conntrack_proto_tcp.c is linearized,
at least in the case of linux-2.6.22.5 from kernel.org.
Therefore buff overflow is still a problem, if not a vulnerability,
in the function of tcp_options(),
as shown in the following code,
static struct sk_buff *ip_frag_reasm(struct ipq *qp, struct net_device *dev)
{
[...]
/*
* head is not linearized,
* 2008-1-11 22:48 by sisi
*/
skb_shinfo(head)->frag_list = head->next;
skb_push(head, head->data - skb_network_header(head));
atomic_sub(head->truesize, &ip_frag_mem);
for (fp=head->next; fp; fp = fp->next) {
head->data_len += fp->len;
head->len += fp->len;
if (head->ip_summed != fp->ip_summed)
head->ip_summed = CHECKSUM_NONE;
else if (head->ip_summed == CHECKSUM_COMPLETE)
head->csum = csum_add(head->csum, fp->csum);
head->truesize += fp->truesize;
atomic_sub(fp->truesize, &ip_frag_mem);
}
head->next = NULL;
head->dev = dev;
head->tstamp = qp->stamp;
iph = ip_hdr(head);
iph->frag_off = 0;
iph->tot_len = htons(len);
IP_INC_STATS_BH(IPSTATS_MIB_REASMOKS);
qp->fragments = NULL;
return head;
[...]
}
Best regards,
Jing
2008/1/4, Jozsef Kadlecsik <[email]kadlec@blackhole.kfki.hu[/email]>:
Hi,
On Mon, 24 Dec 2007, jing zhang wrote:
> buffer overflow is discovered in parsing TCP options,
> in both tcp_sack() and tcp_options() functions,
> implemented in nf_conntrack_proto_tcp.c of linux-2.6.22/23.x
>
> I think it is possible to crash a netfilter-based firewall box with simply
> constructed TCP SYN packet.
[...]
> /*
> If 108-byte TCP SYN packet is received in
> the manner of two frags:
> farg-I, 20-byte-IP + 20-byte-TCP + 24-byte-TCP_OPT
> and tcp->doff assigned to 0xf
>
> farg-II, 20-byte-IP + 16-byte-TCP_OPT + 28-byte-TRASH
>
> then the `ptr' is forcedly assigned to `buff',
> and sizeof(buff) is 40-byte.
> */
[...]
Please note, defragmenting happens before conntrack is called. In other
words these functions never see fragmented packets. Therefore I think
there is no such problem in nf_conntrack_proto_tcp.c.
Best regards,
Jozsef
-
E-mail : [email]kadlec@blackhole.kfki.hu[/email], [email]kadlec@sunserv.kfki.hu[/email]
PGP key : [url]http://www.kfki.hu/~kadlec/pgp_public_key.txt[/url]
Address : KFKI Research Institute for Particle and Nuclear Physics
H-1525 Budapest 114, POB. 49, Hungary

复制代码

static int ksoftirqd(void * __bind_cpu)
{
set_current_state(TASK_INTERRUPTIBLE);
/*
* linux-2.6.23.12
* set_user_nice(current, 1);
*/
[...]
}

复制代码

$
$ mkdir /home/platin
$ vim /home/platin/show_buflow.c
#include <linux/module.h>
#include <linux/kernel.h>
#define SHOW_BUF_MAX 3
static char *buff[] = {
[0 ... SHOW_BUF_MAX -2] = "aaa",
[SHOW_BUF_MAX -1] = "and what?",
};
static int __init show_buflow_start(void)
{
int j;
for (j = 0; j < SHOW_BUF_MAX; j++)
printk("%s\n", buff[j]);
printk("%s\n", buff[j+3]);
return 0;
}
static void __exit show_buflow_finish(void) {}
module_init(show_buflow_start);
module_exit(show_buflow_finish);
$ echo obj-m=show_buflow.o >> /home/platin/Makefile
$ make -C /usr/src/linux-2.6.23.12 M=/home/platin modules
$ insmod /home/platin/show_buflow.ko
$

复制代码

localhost test # insmod show_buflow.ko
段错误
localhost test # lsmod
Module Size Used by
show_buflow 5248 1
pcnet32 31236 0
localhost test # rmmod show_buflow
ERROR: Module show_buflow is in use
localhost test #

复制代码

Jan 15 11:42:15 localhost show_buflow: module license 'unspecified' taints kernel.
Jan 15 11:42:15 localhost aaa
Jan 15 11:42:15 localhost aaa
Jan 15 11:42:15 localhost and what?
Jan 15 11:42:15 localhost BUG: unable to handle kernel paging request at virtual address 74616877
Jan 15 11:42:15 localhost printing eip:
Jan 15 11:42:15 localhost c01e6737
Jan 15 11:42:15 localhost *pde = 00000000
Jan 15 11:42:15 localhost Oops: 0000 [#1]
Jan 15 11:42:15 localhost PREEMPT SMP
Jan 15 11:42:15 localhost Modules linked in: show_buflow(P) pcnet32
Jan 15 11:42:15 localhost CPU: 0
Jan 15 11:42:15 localhost EIP: 0060:[<c01e6737>] Tainted: P VLI
Jan 15 11:42:15 localhost EFLAGS: 00010097 (2.6.21-gentoo-r4 #56)
Jan 15 11:42:15 localhost EIP is at vsnprintf+0x2af/0x48c
Jan 15 11:42:15 localhost eax: 74616877 ebx: ffffffff ecx: 74616877 edx: fffffffe
Jan 15 11:42:15 localhost esi: c04d26c0 edi: c4b63eb0 ebp: ffffffff esp: c4b63dc4
Jan 15 11:42:15 localhost ds: 007b es: 007b fs: 00d8 gs: 0033 ss: 0068
Jan 15 11:42:15 localhost Process insmod (pid: 6658, ti=c4b62000 task=cfeb1580 task.ti=c4b62000)
Jan 15 11:42:15 localhost Stack: 00000000 cfeb7070 cfeb7070 1b41a784 00000109 0000f6d7 00000400 c04d26c0
Jan 15 11:42:15 localhost 0051e0c0 c4b63e0c c04d2ac0 ffffffff 00000000 d0855051 00000400 cf402c00
Jan 15 11:42:15 localhost cf402d98 d0855280 c01e69fd c4b63eb0 00000003 c011e412 c4b63eb0 cf51e0c0
Jan 15 11:42:15 localhost Call Trace:
Jan 15 11:42:15 localhost [<c01e69fd>] vscnprintf+0x14/0x1f
Jan 15 11:42:15 localhost [<c011e412>] vprintk+0xbd/0x2fc
Jan 15 11:42:15 localhost [<c01195f0>] try_to_wake_up+0x393/0x39d
Jan 15 11:42:15 localhost [<c033b0a8>] preempt_schedule+0x46/0x58
Jan 15 11:42:15 localhost [<c01195f0>] try_to_wake_up+0x393/0x39d
Jan 15 11:42:15 localhost [<c033b05a>] wait_for_completion+0x93/0x9b
Jan 15 11:42:15 localhost [<c033c911>] _spin_unlock_irq+0xe/0x22
Jan 15 11:42:15 localhost [<c011e66c>] printk+0x1b/0x1f
Jan 15 11:42:15 localhost [<d0855038>] init_module+0x38/0x40 [show_buflow]
Jan 15 11:42:15 localhost [<c01395e5>] sys_init_module+0x15ac/0x16e3
Jan 15 11:42:15 localhost [<c033c767>] _spin_lock+0xd/0x5a
Jan 15 11:42:15 localhost [<c011e651>] printk+0x0/0x1f
Jan 15 11:42:15 localhost [<c0159fa7>] __fput+0x112/0x13c
Jan 15 11:42:15 localhost [<c016ac25>] mntput_no_expire+0x11/0x5c
Jan 15 11:42:15 localhost [<c0104e20>] sysenter_past_esp+0x5d/0x81
Jan 15 11:42:15 localhost =======================
Jan 15 11:42:15 localhost Code: 74 24 28 73 03 c6 06 20 46 4d 85 ed 7f f1 e9 b9 00 00 00 8b 0f 81 f9 ff 0f 00 00 b8 2e 51 3d c0 0f 46 c8 8b 54 24 2c 89 c8 eb 06 <80> 38 00 74 07 40 4a 83 fa ff 75 f4 29 c8 89 c3 89 e8 f6 44 24
Jan 15 11:42:15 localhost EIP: [<c01e6737>] vsnprintf+0x2af/0x48c SS:ESP 0068:c4b63dc4
Jan 15 11:42:15 localhost note: insmod[6658] exited with preempt_count 2
Jan 15 11:42:15 localhost BUG: scheduling while atomic: insmod/0x10000002/6658
Jan 15 11:42:15 localhost [<c033a806>] __sched_text_start+0x56/0x7c3
Jan 15 11:42:15 localhost [<c02e70f0>] net_rx_action+0x13c/0x181
Jan 15 11:42:15 localhost [<c0119a38>] __cond_resched+0x12/0x2c
Jan 15 11:42:15 localhost [<c033b575>] cond_resched+0x26/0x31
Jan 15 11:42:15 localhost [<c0148961>] unmap_vmas+0x415/0x514
Jan 15 11:42:15 localhost [<c014b307>] exit_mmap+0x7c/0x108
Jan 15 11:42:15 localhost [<c011bcd0>] mmput+0x1d/0x78
Jan 15 11:42:15 localhost [<c0120623>] do_exit+0x1ae/0x6ad
Jan 15 11:42:15 localhost [<c010638b>] die+0x208/0x22d
Jan 15 11:42:15 localhost [<c033e362>] do_page_fault+0x442/0x510
Jan 15 11:42:15 localhost [<c033df20>] do_page_fault+0x0/0x510
Jan 15 11:42:15 localhost [<c033cacc>] error_code+0x7c/0x84
Jan 15 11:42:15 localhost [<c01e6737>] vsnprintf+0x2af/0x48c
Jan 15 11:42:15 localhost [<c01e69fd>] vscnprintf+0x14/0x1f
Jan 15 11:42:15 localhost [<c011e412>] vprintk+0xbd/0x2fc
Jan 15 11:42:15 localhost [<c01195f0>] try_to_wake_up+0x393/0x39d
Jan 15 11:42:15 localhost [<c033b0a8>] preempt_schedule+0x46/0x58
Jan 15 11:42:15 localhost [<c01195f0>] try_to_wake_up+0x393/0x39d
Jan 15 11:42:15 localhost [<c033b05a>] wait_for_completion+0x93/0x9b
Jan 15 11:42:15 localhost [<c033c911>] _spin_unlock_irq+0xe/0x22
Jan 15 11:42:15 localhost [<c011e66c>] printk+0x1b/0x1f
Jan 15 11:42:15 localhost [<d0855038>] init_module+0x38/0x40 [show_buflow]
Jan 15 11:42:15 localhost [<c01395e5>] sys_init_module+0x15ac/0x16e3
Jan 15 11:42:15 localhost [<c033c767>] _spin_lock+0xd/0x5a
Jan 15 11:42:15 localhost [<c011e651>] printk+0x0/0x1f
Jan 15 11:42:15 localhost [<c0159fa7>] __fput+0x112/0x13c
Jan 15 11:42:15 localhost [<c016ac25>] mntput_no_expire+0x11/0x5c
Jan 15 11:42:15 localhost [<c0104e20>] sysenter_past_esp+0x5d/0x81
Jan 15 11:42:15 localhost =======================

复制代码

static void add_file(struct super_block *sb, char *name,
int (*func) (struct seq_file *, struct super_block *))
{
struct proc_dir_entry *de;
de = create_proc_entry(name, 0, REISERFS_SB(sb)->procdir);
if (de) {
/*
* linux-2.6.23.12/fs/reiserfs
* 2008-1-18 21:09
* nice play show what is free indeed
*/
de->data = func;
de->proc_fops = &r_file_operations;
}
}

复制代码

// make sure, that the node contents look like a node of
// certain level
if (!is_tree_node(p_s_bh, expected_level)) {
reiserfs_warning(p_s_sb, "vs-5150: search_by_key: "
"invalid format found in block %ld. Fsck?",
p_s_bh->b_blocknr);
pathrelse(p_s_search_path);
/* linux-2.6.23.12
* it is not HW err
*/
return IO_ERROR;
}

复制代码

struct in_core_key
{
__u32 k_dir_id;
__u32 k_objectid;
__u64 k_offset;
__u8 k_type; /* shit and big tail eagle?! */
}; /* shouldbe? __attribute__ ((__packed__)); */
/*linux-2.6.23.12*/
struct cpu_key
{
struct in_core_key on_disk_key;
int version;
int key_length; /* 3 in all cases but direct2indirect and
indirect2direct conversion */
};

复制代码

static int balance_leaf(struct tree_balance *tb,
struct item_head *ih, /* item header of inserted item (this is on little endian) */
const char *body, /* body of inserted item or bytes to paste */
int flag, /* i - insert, d - delete, c - cut, p - paste
(see comment to do_balance) */
struct item_head *insert_key, /* in our processing of one level we sometimes determine what
must be inserted into the next higher level. This insertion
consists of a key or two keys and their corresponding
pointers */
struct buffer_head **insert_ptr /* inserted node-ptrs for the next level */
)
{
struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
int item_pos = PATH_LAST_POSITION(tb->tb_path); /* index into the array of item headers in S[0]
of the affected item */
struct buffer_info bi;
struct buffer_head *S_new[2]; /* new nodes allocated to hold what could not fit into S */
int snum[2]; /* number of items that will be placed
into S_new (includes partially shifted
items) */
int sbytes[2]; /* if an item is partially shifted into S_new then
if it is a directory item
it is the number of entries from the item that are shifted into S_new
else
it is the number of bytes from the item that are shifted into S_new
*/
int n, i;
int ret_val;
int pos_in_item;
int zeros_num;
PROC_INFO_INC(tb->tb_sb, balance_at[0]);
/* Make balance in case insert_size[0] < 0 */
if (tb->insert_size[0] < 0)
return balance_leaf_when_delete(tb, flag);
zeros_num = 0;
if (flag == M_INSERT && body == 0)
/*
* 2008-1-30 21:46
* linux-2.6.23.12
* @@@@@@@@@@@@@@@@@@@@@@@@@@@@
* potential ih NULL pointer @
* @@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
zeros_num = ih_item_len(ih);
pos_in_item = tb->tb_path->pos_in_item;
/* for indirect item pos_in_item is measured in unformatted node
pointers. Recalculate to bytes */
if (flag != M_INSERT
&& is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
pos_in_item *= UNFM_P_SIZE;
[...]
}
int reiserfs_paste_into_item(struct reiserfs_transaction_handle *th,
struct treepath *p_s_search_path, /* Path to the pasted item */
const struct cpu_key *p_s_key, /* Key to search for the needed item */
struct inode *inode, /* Inode that item belongs to */
const char *p_c_body, /* Pointer to the bytes to paste */
int n_pasted_size) /* Size of pasted bytes */
{
[...]
/* Perform balancing after all resources are collected by fix_nodes, and
* accessing them will not risk triggering schedule.
*/
if (retval == CARRY_ON) {
/*
* source-01
*/
do_balance(&s_paste_balance, NULL, /*ih*/ p_c_body, M_PASTE);
return 0;
}
retval = (retval == NO_DISK_SPACE) ? -ENOSPC : -EIO;
[...]
}
void do_balance(struct tree_balance *tb, /* tree_balance structure */
struct item_head *ih, /* item header of inserted item */
const char *body, /* body of inserted item or bytes to paste */
int flag)
/* i - insert, d - delete
c - cut, p - paste
Cut means delete part of an item
(includes removing an entry from a directory).
Delete means delete whole item.
Insert means add a new item into the tree.
Paste means to append to the end of an
existing file or to insert a directory entry.
*/
{
[...]
do_balance_starts(tb);
/* balance leaf returns 0 except
* if combining L R and S into one node.
*
* see balance_internal() for explanation of this line of code.
*/
child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
/*
* source-02
*/
balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
[...]
}

复制代码

static void internal_copy_pointers_items(struct buffer_info *dest_bi,
struct buffer_head *src,
int last_first, int cpy_num)
{
/* ATTENTION! Number of node pointers in DEST is equal to number of items in DEST,
* as delimiting key have already inserted to buffer dest.
*/
struct buffer_head *dest = dest_bi->bi_bh;
int nr_dest, nr_src;
int dest_order, src_order;
struct block_head *blkh;
struct reiserfs_key *key;
struct disk_child *dc;
nr_src = B_NR_ITEMS(src);
RFALSE(dest == NULL || src == NULL,
"src (%p) or dest (%p) buffer is 0", src, dest);
/*
2008-2-9 12:54
linux-2.6.23.12
RFALSE(dest == NULL || src == NULL,
"src (%p) or dest (%p) buffer is 0", src, dest);
nr_src = B_NR_ITEMS(src);
*/
[...]
}

复制代码

simple ops in Stree
Unlike ext2, reiserfs is a modner FS and has attrs:
1, logging
2, extent inode attr
3, acl, posix or not
4, Stree, derived from Btree
Like Btree, Stree consists of nodes and manages nodes,
which only contains meta info. there are two kinds of nodes
in Stree: interal and leaf, and for simplicity the internal
is called node here, following the Btree def.
By def in Stree, node, mapped to phyiscal block(block on disk) by BLKH,
is just a array of KEY+DC(block pointer or disk child), though the format
of the array is funny, and Mr HR, i guess, favorates block ops in crazy manner,
which can be understood since the block_sz can be changed acoording to ur taste.
Unlike node, leaf is used to store four types of items,
1, sd, stat data, or inode, the hot element of FS
2, de, dir entry, also hot
3, direct
4, indirect
compared withext2, nothing is new but the way to manage them.
Lets see a rather simple example on linux cmdline
# echo a >> /mnt_HS/Stree/simple
# echo $?
0
/*
* As in the whitepaper by Mr. HR, it is not simple to show Stree chart though
* charmimg like Nina Reiser, here i do what i can.
*/
and the corresponding image in Stree is
| BLKH[h+2] | P0 | ... | P[h+2] | ... | free space |
where BLKH[h+2] represents the block of block_sz bytes pointed to by root node,
i gas, and P[h+2] to dir `Stree',
| BLKH[h+1] | P0 | ... | PL[h+1] | P[h+1] | PR[h+1] | ... | free space |
where P[h+1] to regular file `simple' or S in HR's dictionary,
simlarly PL[h+1] to L, and PR[h+1] to R, finally and obviuosly h = 0,
in this simple case.
| BLKH[h] | IH-0 | IH-1 | free space | I-1 | I-0 |
where IH for Item Header, and IH-0 is of type `sd',
I-0 is the socalled inode of `simple',
IH-1, i gas, is of type `direct', and its body I-1 is just `a'.
After another operation on `simple'
# echo b >> /mnt_HS/Stree/simple
i gas, the only chg in Stree is IH-1 and its body from `a' to `ab',
lets check what HR did in v-3.6 of linux-2.6.23.12,
/* first, ==========================
ip means Inserting or Pasting
*/
static int ip_check_balance(struct tree_balance *tb, int h)
{
[...]
if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h)
== NO_BALANCING_NEEDED)
/* new item fits into node S[h] without any shifting */
return NO_BALANCING_NEEDED;
[...]
}
/* second, ==========================
*/
static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
struct tree_balance *tb, int h)
{
struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
int levbytes = tb->insert_size[h];
struct item_head *ih;
struct reiserfs_key *r_key = NULL;
ih = B_N_PITEM_HEAD(Sh, 0);
if (tb->CFR[h])
r_key = B_N_PDELIM_KEY(tb->CFR[h], tb->rkey[h]);
/*
* nicer to understand as:
* lfree + rfree < MAX_CHILD_SIZE(Sh) - sfree + levbytes
*/
if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
/* shifting may merge items which might save space */
- ((!h && op_is_left_mergeable(&ih->ih_key, Sh->b_size)) ? IH_SIZE : 0)
- ((!h && r_key && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
+ (h ? KEY_SIZE : 0))
{ /* node can not be removed */
if (sfree >= levbytes) {
/* new item fits into node S[h] without any shifting */
if (!h)
tb->s0num = B_NR_ITEMS(Sh) + ((mode == M_INSERT) ? 1 : 0);
set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
return NO_BALANCING_NEEDED;
}
}
PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
return !NO_BALANCING_NEEDED;
}
Oh Jesus, HR favorates shift much more, and i gas once more,
meta data and balance are concerned by HR much more than file data?
As u see, the code for the two ops, fix_node and do_balance, upon Stree is
hard and harder to read, and i dream dig it no more harder
in v-3.7 in the original track, and U r welcome to my dream.

复制代码

static void create_virtual_node(struct tree_balance *tb, int h)
{
struct item_head *ih;
struct virtual_node *vn = tb->tb_vn;
int new_num;
struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
if (!h) {
create_virtual_leaf(tb, h);
return;
}
/* size of v node */
vn->vn_size = MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh)
+ tb->insert_size[h];
vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
}
static void create_virtual_leaf(struct tree_balance *tb, int h)
{
struct item_head *ih;
struct virtual_node *vn = tb->tb_vn;
int new_num;
struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
vn->vn_size = MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
/* number of items in v node */
vn->vn_nr_item = B_NR_ITEMS(Sh) +
((vn->vn_mode == M_INSERT) ? 1 : 0) -
((vn->vn_mode == M_DELETE) ? 1 : 0);
/* first v item */
vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);
/*
* first item in S[h]
*/
ih = B_N_PITEM_HEAD(Sh, 0);
/*
* define the mergeability for 0-th item,
* if it is not being deleted
*/
if (op_is_left_mergeable(&ih->ih_key, Sh->b_size)
&& (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
/*
* go through all items those remain in the virtual node,
* except for the new (inserted) one
*/
for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
int j;
struct virtual_item *vi = vn->vn_vi + new_num;
int is_affected = new_num == vn->vn_affected_item_num;
if (is_affected && vn->vn_mode == M_INSERT)
continue;
/* get item number in source node */
j = old_item_num(new_num, vn->vn_affected_item_num, vn->vn_mode);
/*
* vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
*
* and its still amazing why IH_SIZE counted even if !is_affected.
*
* Jesus, its used, at least, by check_left/right
for (i = 0; i < vn->vn_nr_item;
i++, ih_size = IH_SIZE, d_size = 0, vi++) {
d_size += vi->vi_item_len;
for (i = vn->vn_nr_item - 1; i >= 0;
i--, d_size = 0, ih_size = IH_SIZE, vi--) {
d_size += vi->vi_item_len;
*
*/
vi->vi_item_len = ih_item_len(ih + j) + IH_SIZE;
vi->vi_ih = ih + j;
vi->vi_item = B_I_PITEM(Sh, ih + j);
vi->vi_uarea = vn->vn_free_ptr;
/*
* FIXME: there is no check, that item operation did not
* consume too much memory
*/
vn->vn_free_ptr +=
op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
reiserfs_panic(tb->tb_sb,
"vs-8030: create_virtual_node: "
"virtual node space consumed");
if (!is_affected) /* this item is not being changed */
continue;
if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
/*vn->vn_vi[new_num].vi_item_len += tb->insert_size[0]; */
vi->vi_item_len += tb->insert_size[0];
vi->vi_new_data = vn->vn_data;
}
}
/* virtual inserted item is not defined yet */
if (vn->vn_mode == M_INSERT) {
struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
RFALSE(vn->vn_ins_ih == 0,
"vs-8040: item header of inserted item is not specified");
vi->vi_item_len = tb->insert_size[0];
vi->vi_ih = vn->vn_ins_ih;
vi->vi_item = vn->vn_data;
vi->vi_uarea = vn->vn_free_ptr;
op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
tb->insert_size[0]);
}
/* set right merge flag we take right delimiting key and
* check whether it is a mergeable item
*/
if (tb->CFR[0]) {
struct reiserfs_key *key;
key = B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]);
if (op_is_left_mergeable(key, Sh->b_size) &&
(vn->vn_mode != M_DELETE ||
vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
vn->vn_vi[vn->vn_nr_item - 1].vi_type |= VI_TYPE_RIGHT_MERGEABLE;
#ifdef CONFIG_REISERFS_CHECK
if (op_is_left_mergeable(key, Sh->b_size) &&
!(vn->vn_mode != M_DELETE
|| vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
/* we delete last item and
* it could be merged with right neighbor's first item
*/
if (!
(B_NR_ITEMS(Sh) == 1
&& is_direntry_le_ih(B_N_PITEM_HEAD(Sh, 0))
&& I_ENTRY_COUNT(B_N_PITEM_HEAD(Sh, 0)) == 1)) {
/* node contains more than 1 item, or item is not directory item, or this item contains more than 1 entry */
print_block(Sh, 0, -1, -1);
reiserfs_panic(tb->tb_sb,
"vs-8045: create_virtual_node: rdkey %k, affected item==%d (mode==%c) Must be %c",
key, vn->vn_affected_item_num,
vn->vn_mode, M_DELETE);
}
}
#endif
}
}

复制代码

static void balance_leaf_do_split(struct tree_balance *tb,
struct item_head *ih,
const char *body,
int flag,
struct item_head *insert_key,
struct buffer_head **insert_ptr)
{
struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
/* index of the affected item */
int item_pos = PATH_LAST_POSITION(tb->tb_path);
struct buffer_info bi;
int n, i, ret_val;
int pos_in_item;
int zeros_num;
struct buffer_head *S_new[2];
int snum[2];
int sbytes[2];
if (!tb->blknum[0])
return;
if (!(flag == M_INSERT || flag == M_PASTE) {
reiserfs_panic(tb->tb_sb,
"PAP-12245: balance_leaf: blknum > 2: unexpectable mode: %s(%d)",
(flag == M_DELETE) ? "DELETE" :
((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
return;
}
RFALSE(tb->blknum[0] < 1 || tb->blknum[0] > 3,
"PAP-12180: blknum can not be %d. It must be in range [1,3]",
tb->blknum[0]);
/* Fill new nodes that appear in place of S[0] */
snum[0] = tb->s1num;
snum[1] = tb->s2num;
sbytes[0] = tb->s1bytes;
sbytes[1] = tb->s2bytes;
for (i = tb->blknum[0] - 2; i >= 0; i--) {
RFALSE(!snum[i], "PAP-12200: snum[%d] == %d. Must be > 0", i, snum[i]);
/* here we shift from S to S_new nodes */
S_new[i] = get_FEB(tb);
/* initialized block type and tree level */
set_blkh_level(B_BLK_HEAD(S_new[i]), DISK_LEAF_NODE_LEVEL);
n = B_NR_ITEMS(tbS0);
if (flag == M_INSERT) {
if (!(n - snum[i] < item_pos)) {
/* new item or it part don't falls into S_new[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], sbytes[i], S_new[i]);
goto next;
}
goto long_tail_insert;
} else {
if (!(n - snum[i] <= item_pos)) {
/* pasted item doesn't fall into S_new[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], sbytes[i], S_new[i]);
goto next;
}
goto long_tail_paste;
}
long_tail_insert:
if (item_pos == n - snum[i] + 1 && sbytes[i] != -1) {
/* part of new item falls into S_new[i] */
int old_key_comp, old_len, r_zeros_number;
const char *r_body;
int version;
/* Move snum[i]-1 items from S[0] to S_new[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i] -1, -1, S_new[i]);
/* Remember key component and item length */
version = ih_version(ih);
old_key_comp = le_ih_k_offset(ih);
old_len = ih_item_len(ih);
/*Calculate key component and item length to insert into S_new[i] */
set_le_ih_k_offset(ih,
le_ih_k_offset(ih) +
((old_len - sbytes[i]) << (is_indirect_le_ih(ih) ?
tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT : 0)));
put_ih_item_len(ih, sbytes[i]);
/* Insert part of the item into S_new[i] before 0-th item */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
if ((old_len - sbytes[i]) > zeros_num) {
r_zeros_number = 0;
r_body = body + (old_len - sbytes[i]) - zeros_num;
} else {
r_body = body;
r_zeros_number = zeros_num - (old_len - sbytes[i]);
zeros_num -= r_zeros_number;
}
leaf_insert_into_buf(&bi, 0, ih, r_body, r_zeros_number);
/* Calculate key component and item length to insert into S[i] */
set_le_ih_k_offset(ih, old_key_comp);
put_ih_item_len(ih, old_len - sbytes[i]);
tb->insert_size[0] -= sbytes[i];
} else { /* whole new item falls into S_new[i] */
/* Shift snum[0] - 1 items to S_new[i] (sbytes[i] of split item) */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i] -1, sbytes[i], S_new[i]);
/* Insert new item into S_new[i] */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
leaf_insert_into_buf(&bi, item_pos - n + snum[i] - 1,
ih, body, zeros_num);
zeros_num = tb->insert_size[0] = 0;
}
goto next;
long_tail_paste:
if (item_pos == n - snum[i] && sbytes[i] != -1) {
/* we must shift part of the appended item */
struct item_head *aux_ih;
RFALSE(ih, "PAP-12210: ih must be 0");
aux_ih = B_N_PITEM_HEAD(tbS0, item_pos);
if (is_direntry_le_ih(aux_ih)) {
/* we append to directory item */
int entry_count = ih_entry_count(aux_ih);
if (entry_count - sbytes[i] < pos_in_item
&& pos_in_item <= entry_count) {
/* new directory entry falls into S_new[i] */
RFALSE(!tb->insert_size[0],
"PAP-12215: insert_size is already 0");
RFALSE(sbytes[i] - 1 >= entry_count,
"PAP-12220: there are no so much entries (%d), only %d",
sbytes[i] - 1, entry_count);
/* Shift snum[i]-1 items in whole. Shift sbytes[i] directory entries from directory item number snum[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, snum[i],
sbytes[i] - 1, S_new[i]);
/* Paste given directory entry to directory item */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
leaf_paste_in_buffer(&bi, 0,
pos_in_item - entry_count + sbytes[i] - 1,
tb->insert_size[0], body, zeros_num);
/* paste new directory entry */
leaf_paste_entries(bi.bi_bh, 0,
pos_in_item - entry_count + sbytes[i] - 1,
1,
(struct reiserfs_de_head *) body,
body + DEH_SIZE, tb->insert_size[0]);
tb->insert_size[0] = 0;
pos_in_item++;
} else {
/* new directory entry doesn't fall into S_new[i] */
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], sbytes[i], S_new[i]);
}
} else { /* regular object */
int n_shift, n_rem, r_zeros_number;
const char *r_body;
RFALSE(pos_in_item != ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos))
|| tb->insert_size[0] <= 0,
"PAP-12225: item too short or insert_size <= 0");
/* Calculate number of bytes which must be
* shifted from appended item */
n_shift = sbytes[i] - tb->insert_size[0];
if (n_shift < 0)
n_shift = 0;
leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], n_shift, S_new[i]);
/* Calculate number of bytes which must remain
* in body after append to S_new[i] */
n_rem = tb->insert_size[0] - sbytes[i];
if (n_rem < 0)
n_rem = 0;
/* Append part of body into S_new[0] */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
if (n_rem > zeros_num) {
r_zeros_number = 0;
r_body = body + n_rem - zeros_num;
} else {
r_body = body;
r_zeros_number = zeros_num - n_rem;
zeros_num -= r_zeros_number;
}
leaf_paste_in_buffer(&bi, 0, n_shift,
tb->insert_size[0] - n_rem,
r_body, r_zeros_number);
{
/* 2008-2-16 14:19
* itis not easy to format,
* needless to say to debug HR.
*/
struct item_head *tmp;
tmp = B_N_PITEM_HEAD(S_new[i], 0);
if (is_indirect_le_ih(tmp)) {
set_ih_free_space(tmp, 0);
set_le_ih_k_offset(tmp,
le_ih_k_offset(tmp) +
(n_rem << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT)));
} else {
set_le_ih_k_offset(tmp,
le_ih_k_offset(tmp) + n_rem);
}
}
tb->insert_size[0] = n_rem;
if (!n_rem)
pos_in_item++;
}
} else { /* item falls wholly into S_new[i] */
int ret_val;
struct item_head *pasted;
#ifdef CONFIG_REISERFS_CHECK
struct item_head *ih = B_N_PITEM_HEAD(tbS0, item_pos);
if (!is_direntry_le_ih(ih) &&
(pos_in_item != ih_item_len(ih)
|| tb->insert_size[0] <= 0))
reiserfs_panic(tb->tb_sb,
"PAP-12235: balance_leaf: pos_in_item must be equal to ih_item_len");
#endif /* CONFIG_REISERFS_CHECK */
ret_val = leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
snum[i], sbytes[i], S_new[i]);
RFALSE(ret_val,
"PAP-12240: unexpected value returned by leaf_move_items (%d)",
ret_val);
/* paste into item */
bi.tb = tb;
bi.bi_bh = S_new[i];
bi.bi_parent = NULL;
bi.bi_position = 0;
leaf_paste_in_buffer(&bi, item_pos - n + snum[i],
pos_in_item,
tb->insert_size[0],
body, zeros_num);
pasted = B_N_PITEM_HEAD(S_new[i], item_pos - n + snum[i]);
if (is_direntry_le_ih(pasted))
leaf_paste_entries(bi.bi_bh,
item_pos - n + snum[i],
pos_in_item, 1,
(struct reiserfs_de_head *)body,
body + DEH_SIZE,
tb->insert_size[0]);
/* if we paste to indirect item update ih_free_space */
if (is_indirect_le_ih(pasted))
set_ih_free_space(pasted, 0);
zeros_num = tb->insert_size[0] = 0;
}
goto next;
next:
memcpy(insert_key + i, B_N_PKEY(S_new[i], 0), KEY_SIZE);
insert_ptr[i] = S_new[i];
RFALSE(!buffer_journaled(S_new[i])
|| buffer_journal_dirty(S_new[i])
|| buffer_dirty(S_new[i]),
"PAP-12247: S_new[%d] : (%b)", i, S_new[i]);
} /* for loop */
}

复制代码

static void balance_leaf_shift_right(struct tree_balance *tb,
struct item_head *ih,
const char *body,
int flag,
struct item_head *insert_key,
struct buffer_head **insert_ptr)
{
struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
/* index of the affected item */
int item_pos = PATH_LAST_POSITION(tb->tb_path);
struct buffer_info bi;
int n, ret_val;
int pos_in_item;
int zeros_num;
if (!(tb->rnum[0] > 0)) /* right shift not needed */
return;
zeros_num = 0;
if (flag == M_INSERT && body == 0)
zeros_num = ih_item_len(ih);
pos_in_item = tb->tb_path->pos_in_item;
/* for indirect item pos_in_item is measured in unformatted node
* pointers. Recalculate to bytes
*/
if (flag != M_INSERT &&
is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
pos_in_item *= UNFM_P_SIZE;
n = B_NR_ITEMS(tbS0);
if (flag == M_INSERT) {
if (!(n - tb->rnum[0] < item_pos)) {
/* new item or part of it doesn't fall into R[0] */
leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
return;
}
if (!(item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1)) {
/* whole new item falls into R[0] */
/* Shift rnum[0]-1 items to R[0] */
ret_val = leaf_shift_right(tb, tb->rnum[0] -1, tb->rbytes);
/* Insert new item into R[0] */
bi.tb = tb;
bi.bi_bh = tb->R[0];
bi.bi_parent = tb->FR[0];
bi.bi_position = get_right_neighbor_position(tb, 0);
leaf_insert_into_buf(&bi, item_pos - n + tb->rnum[0] - 1,
ih, body, zeros_num);
if (item_pos - n + tb->rnum[0] - 1 == 0) {
replace_key(tb, tb->CFR[0], tb->rkey[0],
tb->R[0], 0);
}
zeros_num = tb->insert_size[0] = 0;
} else {
loff_t old_key_comp, old_len, r_zeros_number;
const char *r_body;
int version;
loff_t offset;
leaf_shift_right(tb, tb->rnum[0] -1, -1);
version = ih_version(ih);
/* Remember key component and item length */
old_key_comp = le_ih_k_offset(ih);
old_len = ih_item_len(ih);
/* Calculate key component and item length to insert into R[0] */
offset = le_ih_k_offset(ih) +
((old_len - tb->rbytes) << (is_indirect_le_ih(ih) ?
tb->tb_sb-> s_blocksize_bits - UNFM_P_SHIFT : 0));
set_le_ih_k_offset(ih, offset);
put_ih_item_len(ih, tb->rbytes);
/* Insert part of the item into R[0] */
bi.tb = tb;
bi.bi_bh = tb->R[0];
bi.bi_parent = tb->FR[0];
bi.bi_position = get_right_neighbor_position(tb, 0);
if ((old_len - tb->rbytes) > zeros_num) {
r_zeros_number = 0;
r_body = body + (old_len - tb->rbytes) - zeros_num;
} else {
r_body = body;
r_zeros_number = zeros_num - (old_len - tb->rbytes);
zeros_num -= r_zeros_number;
}
leaf_insert_into_buf(&bi, 0, ih, r_body, r_zeros_number);
/* Replace right delimiting key by first key in R[0] */
replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
/* Calculate key component and item length to insert into S[0] */
set_le_ih_k_offset(ih, old_key_comp);
put_ih_item_len(ih, old_len - tb->rbytes);
tb->insert_size[0] -= tb->rbytes;
}
}
else if (flag == M_PASTE) {
if (!(n - tb->rnum[0] <= item_pos)) {
/* new item doesn't fall into R[0] */
leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
}
else if (!(item_pos == n - tb->rnum[0] && tb->rbytes != -1)) {
/* pasted item in whole falls into R[0] */
struct item_head *pasted;
ret_val = leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
/* append item in R[0] */
/* if (pos_in_item >= 0) */ {
bi.tb = tb;
bi.bi_bh = tb->R[0];
bi.bi_parent = tb->FR[0];
bi.bi_position = get_right_neighbor_position(tb, 0);
leaf_paste_in_buffer(&bi, item_pos - n + tb->rnum[0],
pos_in_item, tb->insert_size[0],
body, zeros_num);
}
/* paste new entry, if item is directory item */
pasted = B_N_PITEM_HEAD(tb->R[0], item_pos - n + tb->rnum[0]);
if (is_direntry_le_ih(pasted) && pos_in_item >= 0) {
leaf_paste_entries(bi.bi_bh, item_pos - n + tb->rnum[0],
pos_in_item, 1,
(struct reiserfs_de_head *)body,
body + DEH_SIZE,
tb->insert_size[0]);
if (!pos_in_item) {
RFALSE(item_pos - n + tb->rnum[0],
"PAP-12165: directory item must be first item of node when pasting is in 0th position");
/* update delimiting keys */
replace_key(tb, tb->CFR[0], tb->rkey[0],
tb->R[0], 0);
}
}
if (is_indirect_le_ih(pasted))
set_ih_free_space(pasted, 0);
zeros_num = tb->insert_size[0] = 0;
}
else if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) {
/* we append to directory item */
int entry_count;
RFALSE(zeros_num,
"PAP-12145: invalid parameter in case of a directory");
entry_count = I_ENTRY_COUNT(B_N_PITEM_HEAD(tbS0, item_pos));
if (entry_count - tb->rbytes < pos_in_item) {
/* new directory entry falls into R[0] */
int paste_entry_position;
RFALSE(tb->rbytes - 1 >= entry_count ||
!tb->insert_size[0],
"PAP-12150: no enough of entries to shift to R[0]: rbytes=%d, entry_count=%d",
tb->rbytes, entry_count);
/* Shift rnum[0] items in whole.
* Shift rbytes-1 directory entries from directory item number rnum[0] */
leaf_shift_right(tb, tb->rnum[0], tb->rbytes -1);
/* Paste given directory entry to directory item */
paste_entry_position = pos_in_item - entry_count +
tb->rbytes - 1;
bi.tb = tb;
bi.bi_bh = tb->R[0];
bi.bi_parent = tb->FR[0];
bi.bi_position = get_right_neighbor_position(tb, 0);
leaf_paste_in_buffer(&bi, 0, paste_entry_position,
tb->insert_size[0],
body, zeros_num);
/* paste entry */
leaf_paste_entries(bi.bi_bh, 0,
paste_entry_position, 1,
(struct reiserfs_de_head *) body,
body + DEH_SIZE,
tb->insert_size[0]);
if (paste_entry_position == 0) {
/* change delimiting keys */
replace_key(tb, tb->CFR[0], tb->rkey[0],
tb->R[0], 0);
}
tb->insert_size[0] = 0;
pos_in_item++;
} else { /* new directory entry doesn't fall into R[0] */
leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
}
} else { /* regular object */
int n_shift, n_rem, r_zeros_number;
const char *r_body;
/* Calculate number of bytes which must be
* shifted from appended item */
n_shift = tb->rbytes - tb->insert_size[0];
if (n_shift < 0)
n_shift = 0;
RFALSE(pos_in_item != ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)),
"PAP-12155: invalid position to paste. ih_item_len=%d, pos_in_item=%d",
pos_in_item, ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)));
leaf_shift_right(tb, tb->rnum[0], n_shift);
/* Calculate number of bytes which must remain in body
* after appending to R[0] */
n_rem = tb->insert_size[0] - tb->rbytes;
if (n_rem < 0)
n_rem = 0;
{
int version;
unsigned long temp_rem = n_rem;
version = ih_version(B_N_PITEM_HEAD(tb->R[0], 0));
if (is_indirect_le_key(version, B_N_PKEY(tb->R[0], 0)))
temp_rem = n_rem << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT);
set_le_key_k_offset(version, B_N_PKEY(tb->R[0], 0),
le_key_k_offset(version, B_N_PKEY(tb->R[0], 0)) + temp_rem);
set_le_key_k_offset(version, B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0]),
le_key_k_offset(version, B_N_PDELIM_KEY(tb->CFR[0], tb->rkey[0])) + temp_rem);
}
/*
k_offset (B_N_PKEY(tb->R[0],0)) += n_rem;
k_offset (B_N_PDELIM_KEY(tb->CFR[0],tb->rkey[0])) += n_rem;
*/
do_balance_mark_internal_dirty(tb, tb->CFR[0], 0);
/* Append part of body into R[0] */
bi.tb = tb;
bi.bi_bh = tb->R[0];
bi.bi_parent = tb->FR[0];
bi.bi_position = get_right_neighbor_position(tb, 0);
if (n_rem > zeros_num) {
r_zeros_number = 0;
r_body = body + n_rem - zeros_num;
} else {
r_body = body;
r_zeros_number = zeros_num - n_rem;
zeros_num -= r_zeros_number;
}
leaf_paste_in_buffer(&bi, 0, n_shift,
tb->insert_size[0] - n_rem,
r_body, r_zeros_number);
if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->R[0], 0))) {
#if 0
RFALSE(n_rem, "PAP-12160: paste more than one unformatted node pointer");
#endif
set_ih_free_space(B_N_PITEM_HEAD(tb->R[0], 0), 0);
}
tb->insert_size[0] = n_rem;
if (!n_rem)
pos_in_item++;
}
}
else {
reiserfs_panic(tb->tb_sb,
"PAP-12175: balance_leaf: rnum > 0: unexpectable mode: %s(%d)",
(flag == M_DELETE) ? "DELETE" :
((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
}
}

复制代码

/*
* @ih, item header of inserted item, this is on little endian
* @body, body of inserted item or bytes to paste
* @flag, i - insert, d - delete, c - cut, p - paste, see comment to do_balance
* @insert_key, in our processing of one level,
* we sometimes determine what must be inserted into the next higher level.
* This insertion consists of a key or two keys and
* their corresponding pointers.
* @insert_ptr, inserted node-ptrs for the next level
*/
static void balance_leaf_shift_left(struct tree_balance *tb,
struct item_head *ih,
const char *body,
int flag,
struct item_head *insert_key,
struct buffer_head **insert_ptr)
{
struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
/* index of the affected item */
int item_pos = PATH_LAST_POSITION(tb->tb_path);
struct buffer_info bi;
int ret_val;
int pos_in_item;
int zeros_num;
if (!(tb->lnum[0] > 0)) /* left shift not needed */
return;
zeros_num = 0;
if (flag == M_INSERT && body == 0)
zeros_num = ih_item_len(ih);
pos_in_item = tb->tb_path->pos_in_item;
/* for indirect item pos_in_item is measured in unformatted node
* pointers. Recalculate to bytes
*/
if (flag != M_INSERT &&
is_indirect_le_ih(B_N_PITEM_HEAD(tbS0, item_pos)))
pos_in_item *= UNFM_P_SIZE;
/*
* lets compare the affted item with lnum[h] computed in fix_node.
*
* left shift, defed by Hans, as to
* move lnum[h] items starting at I-0 in S to L
*/
if (!(item_pos < tb->lnum[0])) {
/* new item doesn't fall into L[0] */
leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
return;
}
n = B_NR_ITEMS(tb->L[0]);
if (flag == M_INSERT) {
if (item_pos == tb->lnum[0] -1 && tb->lbytes != -1) {
/* part of new item falls into L[0] */
int new_item_len;
int version;
/* shift lnum[0]-1 items entirely */
ret_val = leaf_shift_left(tb, tb->lnum[0] -1, -1);
/* Calculate item length to insert to S[0] */
new_item_len = ih_item_len(ih) - tb->lbytes;
/* Calculate and check item length to insert to L[0] */
put_ih_item_len(ih, tb->lbytes /*ih_item_len(ih) - new_item_len*/);
RFALSE(tb->lbytes <= 0,
"PAP-12080: there is nothing to insert into L[0]: ih_item_len=%d",
ih_item_len(ih));
/* Insert new item into L[0] */
bi.tb = tb;
bi.bi_bh = tb->L[0];
bi.bi_parent = tb->FL[0];
bi.bi_position = get_left_neighbor_position(tb, 0);
leaf_insert_into_buf(&bi, n + item_pos - ret_val,
ih, body,
zeros_num > ih_item_len(ih) ?
ih_item_len(ih) : zeros_num);
version = ih_version(ih);
/* Calculate key component,
* item length and body to insert into S[0]
*/
set_le_ih_k_offset(ih,
le_ih_k_offset(ih) +
(tb->lbytes << (is_indirect_le_ih(ih) ?
tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT : 0)));
put_ih_item_len(ih, new_item_len);
if (tb->lbytes > zeros_num) {
body += (tb->lbytes - zeros_num);
zeros_num = 0;
} else
zeros_num -= tb->lbytes;
RFALSE(ih_item_len(ih) <= 0,
"PAP-12085: there is nothing to insert into S[0]: ih_item_len=%d",
ih_item_len(ih));
} else {
/* new item in whole falls into L[0] */
/* Shift lnum[0]-1 items to L[0] */
ret_val = leaf_shift_left(tb, tb->lnum[0] -1, tb->lbytes);
/* Insert new item into L[0] */
bi.tb = tb;
bi.bi_bh = tb->L[0];
bi.bi_parent = tb->FL[0];
bi.bi_position = get_left_neighbor_position(tb, 0);
leaf_insert_into_buf(&bi, n + item_pos - ret_val,
ih, body, zeros_num);
tb->insert_size[0] = 0;
zeros_num = 0;
}
}
else if (flag == M_PASTE) {
if (!(item_pos == tb->lnum[0] -1 && tb->lbytes != -1)) {
/* appended item will be in L[0] in whole */
struct item_head *pasted;
if (!item_pos &&
op_is_left_mergeable(B_N_PKEY(tbS0, 0), tbS0->b_size)) {
/* if we paste into first item of S[0], and
* it is left mergable,
* then increment pos_in_item by the size of
* the last item in L[0]
*/
pasted = B_N_PITEM_HEAD(tb->L[0], n -1);
if (is_direntry_le_ih(pasted))
pos_in_item += ih_entry_count(pasted);
else
pos_in_item += ih_item_len(pasted);
}
/* Shift lnum[0] in whole */
ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
/* Append to body of item in L[0] */
bi.tb = tb;
bi.bi_bh = tb->L[0];
bi.bi_parent = tb->FL[0];
bi.bi_position = get_left_neighbor_position(tb, 0);
leaf_paste_in_buffer(&bi, n + item_pos - ret_val,
pos_in_item, tb->insert_size[0],
body, zeros_num);
/* if appended item is directory, paste entry */
pasted = B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val);
if (is_direntry_le_ih(pasted))
leaf_paste_entries(bi.bi_bh, n + item_pos - ret_val,
pos_in_item, 1,
(struct reiserfs_de_head *)body,
body + DEH_SIZE,
tb->insert_size[0]);
/* if appended item is indirect item,
* put unformatted node into un list
*/
if (is_indirect_le_ih(pasted))
set_ih_free_space(pasted, 0);
tb->insert_size[0] = 0;
zeros_num = 0;
return;
}
/* we must shift the part of the appended item */
if (is_direntry_le_ih(B_N_PITEM_HEAD(tbS0, item_pos))) {
/* case of directory item */
RFALSE(zeros_num,
"PAP-12090: invalid parameter in case of a directory");
if (tb->lbytes > pos_in_item) {
/* new directory entry falls into L[0] */
struct item_head *pasted;
int l_pos_in_item = pos_in_item;
/* Shift lnum[0] items in whole.
* Shift lbytes - 1 entries from given directory item
*/
ret_val = leaf_shift_left(tb, tb->lnum[0], tb->lbytes -1);
if (ret_val && !item_pos) {
pasted = B_N_PITEM_HEAD(tb->L[0], B_NR_ITEMS(tb->L[0]) -1);
l_pos_in_item += I_ENTRY_COUNT(pasted) - (tb->lbytes -1);
}
/* Append given directory entry to directory item */
bi.tb = tb;
bi.bi_bh = tb->L[0];
bi.bi_parent = tb->FL[0];
bi.bi_position = get_left_neighbor_position(tb, 0);
leaf_paste_in_buffer(&bi, n + item_pos - ret_val,
l_pos_in_item,
tb->insert_size[0],
body, zeros_num);
/* previous string prepared space for pasting new entry,
* following string pastes this entry */
/* when we have merge directory item,
* pos_in_item has been changed too */
/* paste new directory entry. 1 is entry number */
leaf_paste_entries(bi.bi_bh, n + item_pos - ret_val,
l_pos_in_item, 1,
(struct reiserfs_de_head *) body,
body + DEH_SIZE,
tb->insert_size[0]);
tb->insert_size[0] = 0;
} else {
/* new directory item doesn't fall into L[0] */
/* Shift lnum[0]-1 items in whole.
* Shift lbytes directory entries from directory item number lnum[0] */
leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
}
/* Calculate new position to append in item body */
pos_in_item -= tb->lbytes;
} else { /* regular object */
RFALSE(tb->lbytes <= 0,
"PAP-12095: there is nothing to shift to L[0]. lbytes=%d",
tb->lbytes);
RFALSE(pos_in_item != ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)),
"PAP-12100: incorrect position to paste: item_len=%d, pos_in_item=%d",
ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)), pos_in_item);
if (tb->lbytes >= pos_in_item) {
/* appended item will be in L[0] in whole */
/* this bytes number must be appended to
* the last item of L[h] */
int l_n = tb->lbytes - pos_in_item;
/* Calculate new insert_size[0] */
tb->insert_size[0] -= l_n;
RFALSE(tb->insert_size[0] <= 0,
"PAP-12105: there is nothing to paste into L[0]. insert_size=%d",
tb->insert_size[0]);
ret_val = leaf_shift_left(tb, tb->lnum[0],
ih_item_len(B_N_PITEM_HEAD(tbS0, item_pos)));
/* Append to body of item in L[0] */
bi.tb = tb;
bi.bi_bh = tb->L[0];
bi.bi_parent = tb->FL[0];
bi.bi_position = get_left_neighbor_position(tb, 0);
leaf_paste_in_buffer(&bi, n + item_pos - ret_val,
ih_item_len(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val)),
l_n, body, zeros_num > l_n ? l_n : zeros_num);
/* 0-th item in S0 can be only of DIRECT type when l_n != 0 */
{
int version;
int temp_l = l_n;
RFALSE(ih_item_len(B_N_PITEM_HEAD(tbS0, 0)),
"PAP-12106: item length must be 0");
RFALSE(comp_short_le_keys(B_N_PKEY(tbS0, 0),
B_N_PKEY(tb->L[0], n + item_pos - ret_val)),
"PAP-12107: items must be of the same file");
if (is_indirect_le_ih(B_N_PITEM_HEAD(tb->L[0], n + item_pos - ret_val)))
temp_l = l_n << (tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT);
/* update key of first item in S0 */
version = ih_version(B_N_PITEM_HEAD(tbS0, 0));
set_le_key_k_offset(version, B_N_PKEY(tbS0, 0),
le_key_k_offset(version, B_N_PKEY(tbS0, 0)) + temp_l);
/* update left delimiting key */
set_le_key_k_offset(version,
B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0]),
le_key_k_offset(version,
B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0])) + temp_l);
}
/* Calculate new body, position in item and insert_size[0] */
if (l_n > zeros_num) {
body += (l_n - zeros_num);
zeros_num = 0;
} else
zeros_num -= l_n;
pos_in_item = 0;
RFALSE(comp_short_le_keys(B_N_PKEY(tbS0, 0),
B_N_PKEY(tb->L[0], B_NR_ITEMS(tb->L[0]) - 1))
|| !op_is_left_mergeable(B_N_PKEY(tbS0, 0), tbS0->b_size)
|| !op_is_left_mergeable(B_N_PDELIM_KEY(tb->CFL[0], tb->lkey[0]), tbS0->b_size),
"PAP-12120: item must be merge-able with left neighboring item");
} else { /* only part of the appended item will be in L[0] */
/* Calculate position in item for append in S[0] */
pos_in_item -= tb->lbytes;
RFALSE(pos_in_item <= 0,
"PAP-12125: no place for paste. pos_in_item=%d",
pos_in_item);
/* Shift lnum[0] items in whole.
* Shift lbytes byte from item number lnum[0] */
leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
}
}
} else {
reiserfs_panic(tb->tb_sb,
"PAP-12130: balance_leaf: lnum > 0: unexpectable mode: %s(%d)",
(flag == M_DELETE) ? "DELETE" :
((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
}
}

复制代码

static void balance_leaf_do_remain(struct tree_balance *tb,
struct item_head *ih,
const char *body,
int flag,
int *p_pos_in_item,
int *p_item_pos,
int *p_zeros_num)
{
struct buffer_info bi;
int zeros_num, item_pos, pos_in_item;
struct item_head *pasted;
struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
if (!(flag == M_INSERT || flag == M_PASTE) {
reiserfs_panic(tb->tb_sb,
"JZ-0001: balance_leaf:unexpectable mode: %s(%d)",
(flag == M_DELETE) ? "DELETE" :
((flag == M_CUT) ? "CUT" : "UNKNOWN"), flag);
return;
}
zeros_num = *p_zeros_num;
item_pos = *p_item_pos;
pos_in_item = *p_pos_in_item;
if (flag == M_INSERT) {
bi.tb = tb;
bi.bi_bh = tbS0;
bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
bi.bi_position = PATH_H_POSITION(tb->tb_path, 1);
/*
* zeros_num maybe chged in shifting
*/
leaf_insert_into_buf(&bi, item_pos, ih, body, zeros_num);
/* If we insert the first key change the delimiting key */
if (item_pos == 0) {
if (tb->CFL[0]) /* can be 0 in reiserfsck */
replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0, 0);
}
goto out;
}
pasted = B_N_PITEM_HEAD(tbS0, item_pos);
/* when directory, may be new entry already pasted */
if (is_direntry_le_ih(pasted)) {
if (0<= pos_in_item && pos_in_item <= ih_entry_count(pasted)) {
RFALSE(!tb->insert_size[0],
"PAP-12260: insert_size is 0 already");
/* prepare space */
bi.tb = tb;
bi.bi_bh = tbS0;
bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
bi.bi_position = PATH_H_POSITION(tb->tb_path, 1);
leaf_paste_in_buffer(&bi, item_pos, pos_in_item,
tb->insert_size[0],
body, zeros_num);
/* paste entry */
leaf_paste_entries(bi.bi_bh, item_pos, pos_in_item, 1,
(struct reiserfs_de_head *)body,
body + DEH_SIZE,
tb->insert_size[0]);
if (!item_pos && !pos_in_item) {
RFALSE(!tb->CFL[0] || !tb->L[0],
"PAP-12270: CFL[0]/L[0] must be specified");
if (tb->CFL[0])
replace_key(tb, tb->CFL[0], tb->lkey[0],
tbS0, 0);
}
tb->insert_size[0] = 0;
}
} else { /* regular object */
if (pos_in_item == ih_item_len(pasted)) {
RFALSE(tb->insert_size[0] <= 0,
"PAP-12275: insert size must not be %d",
tb->insert_size[0]);
bi.tb = tb;
bi.bi_bh = tbS0;
bi.bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
bi.bi_position = PATH_H_POSITION(tb->tb_path, 1);
leaf_paste_in_buffer(&bi, item_pos, pos_in_item,
tb->insert_size[0],
body, zeros_num);
if (is_indirect_le_ih(pasted)) {
#if 0
RFALSE(tb->insert_size[0] != UNFM_P_SIZE,
"PAP-12280: insert_size for indirect item must be %d, not %d",
UNFM_P_SIZE, tb->insert_size[0]);
#endif
set_ih_free_space(pasted, 0);
}
tb->insert_size[0] = 0;
}
#ifdef CONFIG_REISERFS_CHECK
else {
if (tb->insert_size[0]) {
print_cur_tb("12285");
reiserfs_panic(tb->tb_sb,
"PAP-12285: balance_leaf: insert_size must be 0 (%d)",
tb->insert_size[0]);
}
}
#endif
}
out:
*p_item_pos = item_pos;
*p_pos_in_item = pos_in_item;
*p_zeros_num = zeros_num;
}

复制代码