A good C problem

There are numbers from 1 to N in an array. out of these, one of the number gets duplicated and one is missing. The task is to write a program to find out the duplicate number. Conditions: you have to do it in O(n) time without using any auxilary space (array, bitsets, maps etc..)

I tried and then peeped at the solution provided at the site [by Sarin]. You can see the solution here. Nice one.

verifying user space addresses in kernel

We can verify a user space address while executing in kernel by using the following function

int access_ok(int type, const void *addr, unsigned long size);

Defined in <asm/uaccess.h>, this function returns 1 if the address addr is a user space address and 0 if its a kernel space address (talking of the virtual address of course). argument type can be VERIFY_READ in case you ought to read from the address addr and VERIFY_WRITE if you ought to write to the address addr. VERIFY_WRITE is a superset of VERIFY_READ, hence if you need to read as well as write then use VERIFY_WRITE. argument size is the byte size of the data to be read or written.

This comes handy to be used in drivers and should return -EFAULT if the address is a kernel address where you expect a user space address e.g. in implementation of ioctls.

Slab Poisoning

Slab Poisoning is a term popular among linux kernel hackers and refers to the condition caused by using an uninitialized dynamically allocated memory location, mostly a panic (or oops).

How to find if you have a slab poisoning ?

If you have an offending address 0xa5a5a5a5 somewhere in the kernel oops message, you can be almost be sure that you have used an uninitialized dynamically allocated memory somewhere. Similarl, if you see some where the address 0x6b6b6b6b, you can very much be sure of using a freed variable.

Note: This help from the kernel comes only when it is compiled with CONFIG_DEBUG_SLAB  configuration. In this case, each byte of allocated memory is set to 0xa5 before being handed over to the caller and also set to 0x6b when it is freed. Why not 0x00 ? because that hides more bugs than it can help find (See Writing Solid Code and my review on that book).

Using memory tags  before and after the allocated memor, it is possible to tell about any memory overrun or buffer overflow. When kernel debugging is enabled, linux kernel does exactly that.

Sleep/Wakeup and Linux kernel threads

As a part of understanding the scheduling of kernel thread in linux, I wrote following module code.

#include <linux/module.h>
#include <linux/kernel.h>

#define DBG_FN_ENTRY()  \
do { \
printk(KERN_INFO “Inside function [ %s ]\n”, \
__FUNCTION__); \
} while(0)

struct task_struct *sleeping_task = NULL;
int k = 0;
int func(void *s)
{
int i;

for(i=0;i<20;i++) {
printk(“[%d][%s]\n”, i, (char *)s);
if(sleeping_task)
wake_up_process(sleeping_task);
if(i==10) {
sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
}
}
}

int init_module(void)
{
DBG_FN_ENTRY();

kernel_thread(func, (void *)”first”, 0);
kernel_thread(func, (void *)”second”, 0);

return 0;
}

void cleanup_module(void)
{
DBG_FN_ENTRY();
}

This module on compilation and insertion (2.6.17-10-generic) using

insmod hello.ko

produces following output (/var/log/messages) :

Inside function [ init_module ]
[0][first]
[1][first]
[2][first]
[3][first]
[4][first]
[5][first]
[6][first]
[7][first]
[8][first]
[9][first]
[10][first]
[0][second]
[1][second]
[2][second]
[3][second]
[4][second]
[5][second]
[6][second]
[7][second]
[8][second]
[9][second]
[10][second]
[11][first]
[12][first]
[13][first]
[14][first]
[15][first]
[16][first]
[17][first]
[18][first]
[19][first]
[11][second]
[12][second]
[13][second]
[14][second]
[15][second]
[16][second]
[17][second]
[18][second]
[19][second]

Mistakes that I made and rectified to make it work (..arrgh confessions are painful !)

> used schedule()  without changing the task state, task state remained TASK_RUNNING and hence the thread got scheduled again.

> did not wak up the process and hence threads did not get rescheduled, leading to output only upto the counter 10 for both the threads.

I got hold of an article (slightly late..) on LWN about sleeping/wakeup. worth going.

Extracting MAC from IP address

Few days back, I had to find the MAC address of a machine whose IP address I know. Simple solution is to use ARP but the question is how ? One solution that I have is ping the machine and check your ARP cache. e.g. you need to find out the MAC address of machine having IP address, 192.168.16.134, do the following :-

-bash-2.05b# ping -c 1 -s 1 192.168.16.134
PING 192.168.16.134 (192.168.16.134) 1(29) bytes of data.
9 bytes from 192.168.16.134: icmp_seq=1 ttl=255

— 192.168.16.134 ping statistics —
1 packets transmitted, 1 received, 0% packet loss, time 0ms

-bash-2.05b# arp -na
? (192.168.16.134) at 00:0B:2B:1A:D7:36 [ether] on eth0
? (192.168.16.19) at 00:0B:2B:12:BA:DA [ether] on eth0

Nice to have information.

[Updates follow]

From the comment by adoldo I came to know that same thing can be done using following command on linux systems (as root)

arping [IP Address]

When knowledge poures, it poures from everywhere. we can also do an nmap which gives way more information than would be required I think, including ports (hAck3rs’ 0xd31ght)

$ nmap 192.168.16.11

Starting Nmap 4.00 ( http://www.insecure.org/nmap/ ) at 2006-12-07 09:43 AKST
Interesting ports on 192.168.16.11:
(The 1669 ports scanned but not shown below are in state: closed)
PORT STATE SERVICE
22/tcp open ssh
111/tcp open rpcbind
6000/tcp open X11
MAC Address: 00:0F:FE:1B:9B:A7 (G-pro Computer)

Nmap finished: 1 IP address (1 host up) scanned in 1.553 seconds

Cool stuff !

Program to reverse the words in a string

A friend of mine was asked to write the following program in an interview. He asked me how to do it?

Write a program to reverse the order of the words in a given statement (string). e.g. if input string is “India is a great country”, Output should be “country great a is India”.

This is one of the pet string questions in the interviews. I tried the implementation of a neat way of solving the problem. Here it is. Its not noval way. Algorithm uses iteration. Can you write a recursive one ?

Program is simple and self explanatory about the algorithm.

Update: I just tried writing it in shell – Bash.

#!/bin/bash

INSTR=$1
FINALSTR=””
for i in $INSTR; do
TMP=`echo $i | rev`
FINALSTR=”$FINALSTR $TMP”
done

echo IN : $INSTR
echo OUT: $FINALSTR

obfuscated coding

Just got hold of this code from a C programming resource. C really makes a good language for obfuscated code – valid programs which ‘look’ crap !

#include >stdio.h<

main(t,_,a)
char *a;
{return!0<t?t<3?main(-79,-13,a+main(-87,1-_,
main(-86, 0, a+1 )+a)):1,t<_?main(t+1, _, a ):3,main ( -94, -27+t, a
)&&t == 2 ?_<13 ?main ( 2, _+1, “%s %d %d\n” ):9:16:t<0?t<-72?main(_,
t,”@n’+,#’/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+\
,/+#n+,/#;#q#n+,/+k#;*+,/’r :’d*’3,}{w+K w’K:’+}e#’;dq#’l q#’+d’K#!/\
+k#;q#’r}eKK#}w’r}eKK{nl]’/#;#q#n’){)#}w’){){nl]’/+#n’;d}rw’ i;# ){n\
l]!/n{n#’; r{#w’r nc{nl]’/#{l,+’K {rw’ iK{;[{nl]’/w#q#\
n’wk nw’ iwk{KK{nl]!/w{%’l##w#’ i; :{nl]’/*{q#’ld;r’}{nlwb!/*de}’c \
;;{nl’-{}rw]’/+,}##’*}#nc,’,#nw]’/+kd’+e}+;\
#’rdq#w! nr’/ ‘) }+}{rl#'{n’ ‘)# }’+}##(!!/”)
:t<-50?_==*a ?putchar(a[31]):main(-65,_,a+1):main((*a == ‘/’)+t,_,a\
+1 ):0<t?main ( 2, 2 , “%s”):*a==’/’||main(0,main(-61,*a, “!ek;dc \
i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry”),a+1);}

I soon will try hands on writing some obfuscated code. Purpose is kick & fun. Thats why I do most things in my life !

Btw, you can copy the program, compile it and execute to see the meaningful output.

Stocks: Harrisons Malayalam

I came to know about this growing plantations company in south india. Its a part of the reputed RPG group. Following are few good words by Roshan :-

It owns large plantations in South India, is part of the RPG group. South india is where I see property prices zooming in the future- it’s far safer and has a much better political environment as compared to the rest of India. The stock is trading at a P/E of 2.2 inspite of this being an asset heavy business. The entire business is worth about 150 crores. In my opinion based on land value itself it should touch 1000 crores in market cap soon and 3000-4000 crores in the not so distant future as the P/E rerates to take account of the underlying asset base.

Touch wood. Just bought a few stocks of the company. Website of the company is here. Details about Investors/Share holders is here.