System Call Layer¶

Working with glibc¶

Introduction¶

Why this chapter¶

What is glibc¶

glibc is a library which has a lot of functions pre-written for you so that you do not have to write the code again and again. Also it standardizes the way you should be writing your code. It wraps a lot of system specific details and all you need to know is to how to call the particular function, and what to be expected from the function and what are the return values the function will give you.

glibc is the GNU Version of Standard C Library. All the functions supported in Standard C Library can be found there + some added by the GNU

Todo

Give an example of a function in Standard C and Not in GNU LibC

Todo

Give an example of a function in GLIBC and not in Standard C.

For example: Let us say that we have to find the length of a string. Now this is quite a small code to write and we can write the whole thing ourself, but it is a function which will be used a lot of time accross a lot of products. So the library gives you an implementation of this. As the function is present in the library you can safely assume that the function will work fine because of millions of people have used it and tested it.

For the sake of understanding it better we will now go into the code of the library function and see if its similar to our code.

Also we will make some changes to the code so that it stops working incorrectly and then use it in our programs. This exercise is just a demostration of the following.

• We can read the code of glibc.
• We can compile the code of glibc ourselves and use the newly compiled library.
• We can change the code of glibc.
• We can use the changed code of glibc.

Download, Extract and walk through glibc¶

Download and extract glibc¶

The source code of glibc is available at https://ftp.gnu.org/gnu/libc/. You can sort the list using Last Modified to get the latest tar package.

From the page I got the link as https://ftp.gnu.org/gnu/libc/glibc-2.24.tar.xz.

• Let us download this source, see the following snippet for the exact commands.

$ wget https://ftp.gnu.org/gnu/libc/glibc-2.24.tar.xz
--2017-01-29 07:50:02--  https://ftp.gnu.org/gnu/libc/glibc-2.24.tar.xz
Resolving ftp.gnu.org (ftp.gnu.org)... 208.118.235.20, 2001:4830:134:3::b
Connecting to ftp.gnu.org (ftp.gnu.org)|208.118.235.20|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 13554048 (13M) [application/x-tar]
Saving to: ‘glibc-2.24.tar.xz’

glibc-2.24.tar.xz                     100%[==>]  12.93M   709KB/s    in 21s

2017-01-29 07:50:26 (622 KB/s) - ‘glibc-2.24.tar.xz’ saved [13554048/13554048]

Extract the code¶

• The downloaded code is a compressed tar file. We need to extract it.

rishi@rishi-VirtualBox:~$ tar -xf glibc-2.24.tar.xz

• This creates a directory names glibc-2.24 in the folder.

Walkthrough glibc¶

rishi@rishi-VirtualBox:~$ cd glibc-2.24/
rishi@rishi-VirtualBox:~/glibc-2.24$ ls
abi-tags          ChangeLog.3                        ChangeLog.old-ports-mips
aclocal.m4        ChangeLog.4                        ChangeLog.old-ports-powerpc
argp              ChangeLog.5                        ChangeLog.old-ports-tile
assert            ChangeLog.6                        config.h.in
benchtests        ChangeLog.7                        config.make.in
bits              ChangeLog.8                        configure
BUGS              ChangeLog.9                        configure.ac
catgets           ChangeLog.old-ports                conform
ChangeLog         ChangeLog.old-ports-aarch64        CONFORMANCE
ChangeLog.1       ChangeLog.old-ports-aix            COPYING
ChangeLog.10      ChangeLog.old-ports-alpha          COPYING.LIB
ChangeLog.11      ChangeLog.old-ports-am33           cppflags-iterator.mk
ChangeLog.12      ChangeLog.old-ports-arm            crypt
ChangeLog.13      ChangeLog.old-ports-cris           csu
ChangeLog.14      ChangeLog.old-ports-hppa           ctype
ChangeLog.15      ChangeLog.old-ports-ia64           debug
ChangeLog.16      ChangeLog.old-ports-linux-generic  dirent
ChangeLog.17      ChangeLog.old-ports-m68k           dlfcn
ChangeLog.2       ChangeLog.old-ports-microblaze     elf
extra-lib.mk      LICENSES     nscd                  stdio-common
extra-modules.mk  locale       nss                   stdlib
gen-locales.mk    localedata   o-iterator.mk         streams
gmon              login        po                    string
gnulib            mach         posix                 sunrpc
grp               Makeconfig   PROJECTS              sysdeps
gshadow           Makefile     pwd                   sysvipc
hesiod            Makefile.in  README                termios
hurd              Makerules    resolv          test-skeleton
iconv             malloc       resource        time
iconvdata         manual       rt              timezone
include           math         Rules           version.h
inet              mathvec      scripts         wcsmbs
INSTALL           misc         setjmp          wctype
intl              NAMESPACE    shadow          WUR-REPORT
io                NEWS         shlib-versions
libc-abis         nis          signal
libidn            nptl         socket
libio             nptl_db      soft-fp

Some string related code is here

rishi@rishi-VirtualBox:~/glibc-2.24$ ls string/str*
string/stratcliff.c    string/strcmp.c     string/strerror_l.c      string/strncase_l.c  string/strrchr.c    string/str-two-way.h
string/strcasecmp.c    string/strcoll.c    string/strfry.c          string/strncat.c     string/strsep.c     string/strverscmp.c
string/strcasecmp_l.c  string/strcoll_l.c  string/string.h          string/strncmp.c     string/strsignal.c  string/strxfrm.c
string/strcasestr.c    string/strcpy.c     string/string-inlines.c  string/strncpy.c     string/strspn.c     string/strxfrm_l.c
string/strcat.c        string/strcspn.c    string/strings.h         string/strndup.c     string/strstr.c
string/strchr.c        string/strdup.c     string/strlen.c          string/strnlen.c     string/strtok.c
string/strchrnul.c     string/strerror.c   string/strncase.c        string/strpbrk.c     string/strtok_r.c

Some math related code is here

$ ls math/w_*
math/w_acos.c    math/w_atanhf.c  math/w_fmodf.c   math/w_j1l.c             math/w_lgammal_r.c    math/w_logf.c        math/w_scalblnl.c
math/w_acosf.c   math/w_atanhl.c  math/w_fmodl.c   math/w_jn.c              math/w_lgamma_main.c  math/w_logl.c        math/w_sinh.c
math/w_acosh.c   math/w_cosh.c    math/w_hypot.c   math/w_jnf.c             math/w_lgamma_r.c     math/w_pow.c         math/w_sinhf.c
math/w_acoshf.c  math/w_coshf.c   math/w_hypotf.c  math/w_jnl.c             math/w_log10.c        math/w_powf.c        math/w_sinhl.c
math/w_acoshl.c  math/w_coshl.c   math/w_hypotl.c  math/w_lgamma.c          math/w_log10f.c       math/w_powl.c        math/w_sqrt.c
math/w_acosl.c   math/w_exp10.c   math/w_ilogb.c   math/w_lgamma_compat.c   math/w_log10l.c       math/w_remainder.c   math/w_sqrtf.c
math/w_asin.c    math/w_exp10f.c  math/w_ilogbf.c  math/w_lgamma_compatf.c  math/w_log1p.c        math/w_remainderf.c  math/w_sqrtl.c
math/w_asinf.c   math/w_exp10l.c  math/w_ilogbl.c  math/w_lgamma_compatl.c  math/w_log1pf.c       math/w_remainderl.c  math/w_tgamma.c
math/w_asinl.c   math/w_exp2.c    math/w_j0.c      math/w_lgammaf.c         math/w_log1pl.c       math/w_scalb.c       math/w_tgammaf.c
math/w_atan2.c   math/w_exp2f.c   math/w_j0f.c     math/w_lgammaf_main.c    math/w_log2.c         math/w_scalbf.c      math/w_tgammal.c
math/w_atan2f.c  math/w_exp2l.c   math/w_j0l.c     math/w_lgammaf_r.c       math/w_log2f.c        math/w_scalbl.c
math/w_atan2l.c  math/w_expl.c    math/w_j1.c      math/w_lgammal.c         math/w_log2l.c        math/w_scalbln.c
math/w_atanh.c   math/w_fmod.c    math/w_j1f.c     math/w_lgammal_main.c    math/w_log.c          math/w_scalblnf.c

The header files for the library is here.

$ ls include/
aio.h       ctype.h     fenv.h          grp-merge.h        link.h      netinet     resolv.h          spawn.h           syscall.h   utmp.h
aliases.h   des.h       fmtmsg.h        gshadow.h          list.h      nl_types.h  rounding-mode.h   stab.h            sysexits.h  values.h
alloca.h    dirent.h    fnmatch.h       iconv.h            locale.h    nss.h       rpc               stackinfo.h       syslog.h    wchar.h
argp.h      dlfcn.h     fpu_control.h   ifaddrs.h          malloc.h    nsswitch.h  rpcsvc            stap-probe.h      tar.h       wctype.h
argz.h      elf.h       ftw.h           ifunc-impl-list.h  math.h      obstack.h   sched.h           stdc-predef.h     termios.h   wordexp.h
arpa        endian.h    gconv.h         inline-hashtab.h   mcheck.h    poll.h      scratch_buffer.h  stdio_ext.h       tgmath.h    xlocale.h
assert.h    envz.h      getopt.h        langinfo.h         memory.h    printf.h    search.h          stdio.h           time.h
atomic.h    err.h       getopt_int.h    libc-internal.h    mntent.h    programs    set-hooks.h       stdlib.h          ttyent.h
bits        errno.h     glob.h          libc-symbols.h     monetary.h  protocols   setjmp.h          string.h          uchar.h
byteswap.h  error.h     gmp.h           libgen.h           mqueue.h    pthread.h   sgtty.h           strings.h         ucontext.h
caller.h    execinfo.h  gnu             libintl.h          net         pty.h       shadow.h          stropts.h         ulimit.h
complex.h   fcntl.h     gnu-versions.h  libio.h            netdb.h     pwd.h       shlib-compat.h    stubs-prologue.h  unistd.h
cpio.h      features.h  grp.h           limits.h           netgroup.h  regex.h     signal.h          sys               utime.h

Walkthrough strlen¶

Todo

write this section.

Walkthrough div¶

Todo

write this section.

Walkthrough open¶

Todo

write this section.

Compiling the code of glibc¶

Generally compling and installing code on Linux system involves the following stages

1. Configuring - running configure with right options.
2. Compiling - running make with right options.
3. Install - running make install.

Configuring¶

We will get into the glibc-2.24 source directory and run the configure script. I have intentionally shown the mistakes which happened so that you also understand the small things which needs to be taken care while configuring and compling.

rishi@rishi-VirtualBox:~/glibc-2.24$ ./configure
checking build system type... x86_64-pc-linux-gnu
checking host system type... x86_64-pc-linux-gnu
checking for gcc... gcc
checking for suffix of object files... o
checking whether we are using the GNU C compiler... yes
checking whether gcc accepts -g... yes
checking for readelf... readelf
checking for g++... g++
checking whether we are using the GNU C++ compiler... yes
checking whether g++ accepts -g... yes
checking whether g++ can link programs... yes
configure: error: you must configure in a separate build directory

• We got an error that we should use a separate directory for running configure

rishi@rishi-VirtualBox:~/glibc-2.24$ mkdir ../build_glibc

rishi@rishi-VirtualBox:~/glibc-2.24$ cd ../build_glibc/

• Let us now run the configure command.

rishi@rishi-VirtualBox:~/build_glibc$ ../glibc-2.24/configure
checking build system type... x86_64-pc-linux-gnu
checking host system type... x86_64-pc-linux-gnu
checking for gcc... gcc
checking for suffix of object files... o
checking version of sed... 4.2.2, ok
checking for gawk... no

>>>>>>>>>>>>>>>>>SNIP<<<<<<<<<<<<<<<<<<<<<<

checking if gcc is sufficient to build libc... yes
checking for nm... nm
configure: error:
*** These critical programs are missing or too old: gawk
*** Check the INSTALL file for required versions.

• The configure step gave errors - let us install gawk now.

rishi@rishi-VirtualBox:~/build_glibc$ sudo apt-get install gawk
[sudo] password for rishi:
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following additional packages will be installed:
libsigsegv2
Suggested packages:
gawk-doc
The following NEW packages will be installed:
gawk libsigsegv2

>>>>>>>>>>>>>SNIP<<<<<<<<<<<<<<

Setting up gawk (1:4.1.3+dfsg-0.1) ...

• Check if the command is present.

rishi@rishi-office:~/mydev/publications/system_calls$ which gawk
/usr/bin/gawk

• Let us run configure again

rishi@rishi-VirtualBox:~/build_glibc$ ../glibc-2.24/configure
checking build system type... x86_64-pc-linux-gnu
checking host system type... x86_64-pc-linux-gnu
checking for gcc... gcc
checking for suffix of object files... o
checking whether we are using the GNU C compiler... yes

>>>>>>>>>>SNIP<<<<<<<<<<<<<<<<<<<<<<

running configure fragment for sysdeps/unix/sysv/linux/x86_64
running configure fragment for sysdeps/unix/sysv/linux
checking installed Linux kernel header files... 3.2.0 or later
checking for kernel header at least 2.6.32... ok
*** On GNU/Linux systems the GNU C Library should not be installed into
*** /usr/local since this might make your system totally unusable.
*** We strongly advise to use a different prefix.  For details read the FAQ.
*** If you really mean to do this, run configure again using the extra
*** parameter `--disable-sanity-checks`.

• Configure does not want to overwrite the default library and hence we need to give another directory to install the library.
• Let us make a directory and run the configure script.

rishi@rishi-VirtualBox:~/build_glibc$ mkdir ../install_glibc
rishi@rishi-VirtualBox:~/build_glibc$ ../glibc-2.24/configure --prefix=/home/rishi/install_glibc/
checking build system type... x86_64-pc-linux-gnu
checking host system type... x86_64-pc-linux-gnu
checking for gcc... gcc
checking for suffix of object files... o
configure: creating ./config.status

>>>>>>>SNIP<<<<<<<<<<<<

config.status: creating config.make
config.status: creating Makefile
config.status: creating config.h
config.status: executing default commands

• Configure completed

rishi@rishi-VirtualBox:~/build_glibc$ ls
bits  config.h  config.log  config.make  config.status  Makefile

Compliing¶

• Let us run the make command now.

rishi@rishi-VirtualBox:~/build_glibc$ make -j 16
make -r PARALLELMFLAGS="" -C ../glibc-2.24 objdir=`pwd` all
make[1]: Entering directory '/home/rishi/glibc-2.24'
LC_ALL=C gawk -f scripts/sysd-rules.awk > /home/rishi/build_glibc/sysd-rulesT \



rishi@rishi-VirtualBox:~/build_glibc$ ls
bits  config.h  config.log  config.make  config.status  Makefile
rishi@rishi-VirtualBox:~/build_glibc$
rishi@rishi-VirtualBox:~/build_glibc$
rishi@rishi-VirtualBox:~/build_glibc$



rishi@rishi-VirtualBox:~/build_glibc$ make -j 16
make -r PARALLELMFLAGS="" -C ../glibc-2.24 objdir=`pwd` all
make[1]: Entering directory '/home/rishi/glibc-2.24'
LC_ALL=C gawk -f scripts/sysd-rules.awk > /home/rishi/build_glibc/sysd-rulesT \

    >>>>>>>>>>>>>>>>>>>>>SNIP<<<<<<<<<<<<<<<<<<<
gcc -nostdlib -nostartfiles -o /home/rishi/build_glibc/elf/pldd    -Wl,-z,combreloc -Wl,-z,relro -Wl,--hash-style=both /home/rishi/build_glibc/csu/crt1.o /home/rishi/build_glibc/csu/crti.o `gcc  --print-file-name=crtbegin.o` /home/rishi/build_glibc/elf/pldd.o /home/rishi/build_glibc/elf/xmalloc.o  -Wl,-dynamic-linker=/home/rishi/install_glibc/lib/ld-linux-x86-64.so.2 -Wl,-rpath-link=/home/rishi/build_glibc:/home/rishi/build_glibc/math:/home/rishi/build_glibc/elf:/home/rishi/build_glibc/dlfcn:/home/rishi/build_glibc/nss:/home/rishi/build_glibc/nis:/home/rishi/build_glibc/rt:/home/rishi/build_glibc/resolv:/home/rishi/build_glibc/crypt:/home/rishi/build_glibc/mathvec:/home/rishi/build_glibc/nptl /home/rishi/build_glibc/libc.so.6 /home/rishi/build_glibc/libc_nonshared.a -Wl,--as-needed /home/rishi/build_glibc/elf/ld.so -Wl,--no-as-needed -lgcc  `gcc  --print-file-name=crtend.o` /home/rishi/build_glibc/csu/crtn.o
make[2]: Leaving directory '/home/rishi/glibc-2.24/elf'
make[1]: Leaving directory '/home/rishi/glibc-2.24'

• Make runs successfully.
• Let us check the install_glibc directory. It has nothing in it.

$ ls ../install_glibc/

• Let us run the make install command.

$ make install
LC_ALL=C; export LC_ALL; \
make -r PARALLELMFLAGS="" -C ../glibc-2.24 objdir=`pwd` install
make[1]: Entering directory '/home/rishi/glibc-2.24'
make  subdir=csu -C csu ..=../ subdir_lib
make[2]: Entering directory '/home/rishi/glibc-2.24/csu'
make[2]: Leaving directory '/home/rishi/glibc-

>>>>>>>>>>>SNIP<<<<<<<<<<<<<<<

-f /home/rishi/build_glibc/elf/symlink.list
test ! -x /home/rishi/build_glibc/elf/ldconfig || LC_ALL=C \
/home/rishi/build_glibc/elf/ldconfig  \
/home/rishi/install_glibc/lib /home/rishi/install_glibc/lib
/home/rishi/build_glibc/elf/ldconfig: Warning: ignoring configuration file that cannot be opened: /home/rishi/install_glibc/etc/ld.so.conf: No such file or directory
make[1]: Leaving directory '/home/rishi/glibc-2.24'

Install¶

• Let us now check the install_glibc directory. It has the required files of the new compiled library.

rishi@rishi-VirtualBox:~/build_glibc$ ls ../install_glibc/
bin  etc  include  lib  libexec  sbin

Using the new library¶

Let us now use the above library to link and run our code. We will add a new function to the glibc, change the behaviour of a function in glibc and use the new function and call the changed function.

This will give us a good understanding of how to compile and link with the new library.

Here is the code for adding some changes to the glibc code. See the file glibc-2.24/stdlib/div.c and glibc-2.24/include/stdlib.h.

Here is the diff

glibc-2.24/stdlib/div.c¶

• Here we have added a function my_div which just returns -1 on invokation and have changed the way the function div behaves. Now when we will pass 99 and 99 to div it will return 100 and 100. Read the default behaviour in the man pages.

$ diff glibc-2.24/stdlib/div.c temp/glibc-2.24/stdlib/div.c
51d50
< #include <stdio.h>
59,64d57
<   if (numer == 99 && denom == 99) {
<   printf ("\nValues are 99 and 99");
<   result.quot = 100;
<   result.rem = 100;
<   return result;
<   }
69,74d61
< }
<
<
< int my_div(void) {
<   printf("\n\nCalling my_div() function.");
<   return -1;

• Here is the declaration of the new function.

glibc-2.24/stdlib/stdlib.h¶

$ diff glibc-2.24/stdlib/stdlib.h temp/glibc-2.24/stdlib/stdlib.h
753,754d752
<
< extern int my_div(void);

• Here is the code which calls the functions.

1 2 3 4 5 6 7 8 9 10 11 12

#include <stdio.h> #include <stdlib.h> int main () { div_t result = div(99, 99); int x = my_div(); printf ("\n\nQuotient %d Remainder %d", result.quot, result.rem); return 0; }

• Here is the Makefile which will be used to compile the program.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

TARGET = div OBJ = $(TARGET).o SRC = $(TARGET).c CC = gcc CFLAGS = -g LDFLAGS = -nostdlib -nostartfiles -static GLIBCDIR = /home/rishi/install_glibc/lib/ STARTFILES = $(GLIBCDIR)/crt1.o $(GLIBCDIR)/crti.o `gcc --print-file-name=crtbegin.o` ENDFILES = `gcc --print-file-name=crtend.o` $(GLIBCDIR)/crtn.o LIBGROUP = -Wl,--start-group $(GLIBCDIR)/libc.a -lgcc -lgcc_eh -Wl,--end-group INCDIR = /home/rishi/install_glibc/include $(TARGET): $(OBJ) $(CC) $(LDFLAGS) -o $@ $(STARTFILES) $^ $(LIBGROUP) $(ENDFILES) $(OBJ): $(SRC) $(CC) $(CFLAGS) -c $^ -I `gcc --print-file-name=include` -I $(INCDIR) clean: rm -f *.o *.~ $(TARGET) rm test.c.* rm a.out # https://stackoverflow.com/questions/10763394/how-to-build-a-c-program-using-a-custom-version-of-glibc-and-static-linking/10772056#10772056

• Run the make command.

$ make
gcc -g -c div.c -I `gcc --print-file-name=include` -I /home/rishi/install_glibc/include
gcc -nostdlib -nostartfiles -static -o div /home/rishi/install_glibc/lib//crt1.o /home/rishi/install_glibc/lib//crti.o `gcc --print-file-name=crtbegin.o` div.o -Wl,--start-group /home/rishi/install_glibc/lib//libc.a -lgcc -lgcc_eh -Wl,--end-group `gcc --print-file-name=crtend.o` /home/rishi/install_glibc/lib//crtn.o

• Run the statically linked code

$ ./div

Values are 99 and 99

Calling my_div() function.

Quotient 100 Remainder 100

• See the size of the staticically linked code. The huge size is due to static linking. We will now link it dynamically and then see the size.

$ ls -lh div
-rwxrwxr-x 1 rishi rishi 3.3M Jan 29 20:00 div

• Run the dynamically linked code.

Todo

Link it dynamically.

Error

Unable to do it dynamically.

• See the sizes of the files

rishi@rishi-VirtualBox:~/test_code$ ls -l dynamic-test static-test
-rwxrwxr-x  1 rishi rishi   8600 Jan 29 12:13 dynamic-test
-rwxrwxr-x  1 rishi rishi 909048 Jan 29 12:13 static-test

Todo

Link it dynamically.

• Check the file type of the executables.

Todo

correct the following.

rishi@rishi-VirtualBox:~/test_code$ file static-test
static-test: ELF 64-bit LSB executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.32, BuildID[sha1]=866f4fe367915159ae62cc80a0ae614059d67153, not stripped

rishi@rishi-VirtualBox:~/test_code$ file dynamic-test
dynamic-test: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /home/rishi/install_glibc/lib/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=c0f8ac9a77a879e6adc855333d6bc88c5078ffd3, not stripped

Conclusion¶

In this chapter we have see pretty important things with respect to using glibc. We have see where to find glibc, how to download, extract, make changes and compile the glibc library in your system.

Doing all the steps hands-on will enable you understand the whole workflow more clearly and will thus improve your understanding of systems.

Indices and tables¶

• Index
• Module Index
• Search Page

Table Of Contents

Contents:

• Working with glibc
  • Introduction
  • Why this chapter
  • What is glibc
  • Download, Extract and walk through glibc
  • Download and extract glibc
  • Walkthrough glibc
  • Compiling the code of glibc
  • Using the new library
  • Conclusion

Related Topics

• Documentation overview

©2017, Rishi Agrawal. | Powered by Sphinx 1.5.1 & Alabaster 0.7.9

Problems For Learning Multithreading.

1. Write a function add(int, int) and spawn a new thread to call this function.

   Print the output on the console from the thread.

2. Create a thread routine that adds all the numbers passed to it as argument and return the result to the main thread.

3. Write a program having a global variable x, which is initialised with some

   value, say 10. Now create two threads and increment value of x from both the threads. Also, print the value of x inside thread routines and before main routine finishes. What do you observe? What is the behaviour when program is run multiple times?

4. Write a program having a global variable x, which is initialised with some

   value, say 10. Now create two threads and increment value of x from both the threads. Protect the global variable x using a locking mechanism. Use mutex.

5. Write a program having a global variable x, which is initialised with some

   value, say 10. Now create two threads and increment value of x from both the threads. Protect the global variable x using a locking mechanism. Use spinlock.

6. Open a file and use 5 threads to write to the file. Increase elements in a

   loop in the threads in a loop and write the elements to the file. What is happening here. What should be the data in the file.

7. Open a file and use 5 threads to write to the file. Increase elements in a

   loop in the threads in a loop and write the elements to the file. What is happening here. Make sure that the threads write to the file one by one - for example if the threads are A, B, C, D and E - write the program such that the content of the file is in the order ABCDEABCDE.

8. Using multithreading add all the element of a array. Take a large array say,

   10^8 elements and divide the work across all the threads equally. Compare the time take by a single threaded program.

9. Using multithreading sort a array in ascending order using Merge sort. Take a

   large array, say 1068 elements and compare the working with a single threaded program.

10. Though you are writing multi threaded code - you might observe that some of

    your processor cores are not getting used, and some of your threads are sleeping. How will you - 1. Make sure that all the threads get maximum available resources on your desktop. 2. All the processor cores are busy all the time.

11. What are thread safe functions? Write a function which has a static variable

    • and it increments it. Make it thread safe.

12. What are re-entrant functions? Write a function which has a static variable

    • and it increments it. Make it re-entrant.

13. What are atomic instructions - why are they needed, how do you have atomicity

    in the code. For example in an addition function which has a counter of “How many times it was called”.

14. Open and read a file, keep writing some data using a thread to the file. Now

    whenever you get a keyboard interuppt (for example say ctrl+w) count the number of characters in the file and display it on the screen. This counting has to be done in a new thread. Similiary another thread should calculate the number of words and the number of vowels in the file.

15. Write a multithreaded program where one thread is writing some data to a file,

    and on receiving some interrupt from keyboard (say, ctrl+w), perform following operations using separate threads and display the results on screen: a. Count number of characters written to the file b. Count number of words in the file c. Count number of vowels in the file

    While solving the above question you will observe that you have to take lock on the file. When you take lock - the write thread will be blocked. What do you suggest. How can we minimize the blocking of the write thread. Code them as well.

16. Simulate the consumer - producer problem.
17. Simulate a deadlock situation, the deadlock should be due to improper lock ordering.
18. Implement a mutex library.
19. Implement a spinlock library.
    
    
    Thanks Adheer Chandravanshi<adheerchandravanshi@gmail.com> for reviewing the questions.

Excellence In Programming

Introduction

---

Whether you are a seasoned expert on programming or a newbie, sometimes you need
to redo the basic. This small document is written for redoing the whole thing,
and doing it right, and doing it right in the first attempt.
This book is language independent. Whatever language you are comfortable with -
solve the questions.
The initial programs are quite simple and it lets you spend some time with
basics and slowly picks up pace.
This book is and will be always in construction. I request all the readers to
send me reviews, questions and answers on pinnacle-mentors@googlegroups.com.
Whenever you encounter or solve a small programing question - convert it to a
question and send that to me. I will give proper credits and add the question.

Use the repository https://github.com/abrrba/pinnacle-blogs for checking-in the code.

---

Loops

---

Print the following patterns.

1. ********
   
   ********
   
   ********
   
   ********
   
   ********
   

2. *****
   
   ****
   
   ***
   
   **
   
   *
   

3. *
   
   **
   
   ***
   
   ****
   
   *****
   

4. ####*
   
   ###**
   
   ##***
   
   #****
   
   *****
   

5.     *
   
      **
   
     ***
   
    ****
   
   *****
   

6. ***********
   
   ***** *****
   
   ****   ****
   
   ***     ***
   
   **       **
   
   *         *
   
   **       **
   
   ***     ***
   
   ****   ****
   
   ***** *****
   
   ***********
   

7.     *
   
      ***
   
     *****
   
    *******
   
   *********
   
    *******
   
     *****
   
      ***
   
       *
   

8. *********
   
   *******
   
   *****
   
   ***
   
   *
   

---

Arrays

---

1. Find the sum of all the elements stored in the array?
2. Find the product of all the elements stored in the array? What can be the possible problems here.
3. Find the maximum and minimum element of an array.
4. Find the average of the array.
5. Find the median of the array.
6. Find the element which has occurred for the maximum number of times in an array. Similarly find the element which has occurred minimum number of times.
7. Fill an array with the multiples of 3, then remove the numbers which are divisible by 5. Fill the empty spaces so generated with -1.
8. Fill an array with random elements.
9. How will you solve the second problem of the basic level.
10. Sort the elements stored in the array using all the sorting methods like Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort.
11. Write a program to multiply two 2-D Arrays.
12. Write a program to find the sum of a 2D array
13. Write a program to find the transpose of a 2D Array.
14. Write a program to find the inverse of an array.
15. Write a program to find all the prime numbers in a range of 1 to N. N is the user input.
16. Write a program to find the factorial of a given number.
17. Write a program to find the sum of al the numbers till N ( N is the user input).
18. Print the geomatric progressoion, Take the relevant input.
19. Print the arthimatic progression, take the relevant input.
20. Write a program to convert the epoch to date.
21. Write a program to print the spiral of numbers.
22. Write a program to print the sum of all the numbers in a 2 D array.
23. Write a program to print the multiplication of all the elements in a 2 D array.

---

Character/Sorting Arrays

---

Write a program for

1. Finding the character which is alphabetically highest, use ASCII values.
2. Find wether a string is a palindrome or not.
3. Concat the same string to itself. (Eg. HelloWorld -> HelloWorldHelloWorld) #. Insert the word “Hello” in the middle of the words in an sentence. (Eg. How are You? to How Hello are Hello You hello?)
4. In the above program do not use too much of extra space, do not use a new array.
5. Find if the other string is a substring of the other string.
6. Find the number of words in a string. (use space as a word separator).
7. In the above program, make sure that multiple spaces are counted as one ” ” is counted as ” “
8. Parse a string and find the number of vowels, spaces, special characters.
9. Parse a string and reverse all the words in the string.
10. Reverse the characters of string.

---

Data Structures - Bitmap

---

1. Make a library for bitmap. The function calls will be void * init_bitmap(size_of_bitmap). set_bit(int), unset_bit(int), check_bit(int).
2. Use the bitmap to check for the characters present in a string.
3. Use the bitmap to check for the numbers in a array of integers (1 to N).

---

Data Structures - Arrays

---

1. Implement a small dictionary application where the users can search for the meaning of a word. use linear search.
2. Sort the elements and do not binary search. Implement the above dictionary, find the runtime.
3. Sort the elements and do binary search, check the runtime.

---

Data Structures - Trees

---

1. Implement a binary tree.
2. Implement a binary search tree.
3. Implement a binary search tree library.
4. Using the binary search tree library, make a dictionary. Check the runtime for searching the words
5. If your language support tree as data strutures use the feature and implment a dictionary, See the difference between the runtime. Find out why there is a diference.

---

Data Structures - Hashing

---

1. Implement hashing - use a simple hashing function, make sure that you can handle collisions.
2. Using the above code of hashing, insert the elements of the dictionary in your hash. Check the number of collisions. How can you reduce the collisions.
3. Now with a better algorithm for hashing, test the dictionary words and see the number of collisions.
4. Check the runtime, when you are using your new function.
5. Now use the hsearch() for creating a hash, Now check the runtime.
6. Now use the SHA1 hashing for creating a hash, now check the runtime.

---

Files

---

1. Reverse all the characters in a given file. Use the above written code for string reverse.
2. Reverse all the sentences in a file. Use the above written code. (I love you to you love I).
3. Learn how to read/write a file using C/Java Programming (fopen, fread, fwrite). Write a simple data base application where you save the name, birthDate of students. make another table to save the marks in maths, chemistry, and physics of the students.
4. In the above program, generate the following reports. Number of students failed/passed in the subjects. Topper and the lowest scorer. Find the number of students whose aggregate is more than 90%, 80%. List the students.
5. If you can easily generate graphs (like in Java) then use graphs to show the results. This will make your looping concepts better.
6. Use a file to save the word and the meaning. Whenever user searches for a word, read the file, line by line and then check for the element. Observe the runtime.
7. Use a file to save the word and the meaning, but this time, read the whole file, take the whole contents in ram and then search for the contents.
8. Read the same file, now save the contents in a Hashing table and then search. See the amount of code you could reuse which you wrote earlier. Can that be improved. How? Re-implement the above written code if required.
9. Read the same file, save the contents in a tree and then search. See the amount of code you could reuse which you wrote earlier. Can that be improved. How? Re-implement the above written code if required.
10. Read the same file and save the contents in an array and then search. See the amount of code you could reuse which you wrote earlier. Can that be improved. How? Re-implement the above written code if required.
11. Observe the difference in the run time of the above 3 approaches of writing a dictionary.
12. 
    

---

Read About

---

1. Sieve of Eratosthenes
2. Rabin-Karp algorithm

---

More Problems

---

1. Find the Prime numbers using Sieve of Eratosthenes
2. Find the substring using Rabin-Karp algorithm.