Double Hashing

Double hashing is a collision resolving technique in Open Addressed Hash tables

Double hashing can be done using :
(hash1(key) + i * hash2(key)) % TABLE_SIZE
Here hash1() and hash2() are hash functions and TABLE_SIZE
is size of hash table.
(We repeat by increasing i when collision occurs)

https://www.geeksforgeeks.org/double-hashing/

interview

https://github.com/interviewdiscussion/tag

How to Enable Nested KVM

http://www.rdoxenham.com/?p=275

c Makefile template

# c makefile template SRC_DIR = src OUTPUT_DIR = output TARGETS = mytest.bin SRCS = $(wildcard $(SRC_DIR)/*.c) DEPS = $(addprefix $(OUTPUT_DIR)/, $(patsubst %.c, %.d, $(notdir $(SRCS)))) OBJS = $(addprefix $(OUTPUT_DIR)/, $(patsubst %.c, %.o, $(notdir $(SRCS)))) CFLAGS = -Wall -O2 RM = rm -f -v .PHONY: all all: $(OUTPUT_DIR)/$(TARGETS) $(OUTPUT_DIR)/%.d: $(SRC_DIR)/%.c $(CC) -MM $(CFLAGS) $< | sed 's,$*\.o[ :]*,$(basename $@).o $@: ,g' > $@; \ echo "compile .d file: $@" -include $(DEPS) $(OUTPUT_DIR)/%.o: $(SRC_DIR)/%.c $(COMPILE.c) $(OUTPUT_OPTION) $<; \ echo "compile .o file: $@" $(OUTPUT_DIR)/$(TARGETS): $(OBJS) $(LINK.o) $(OUTPUT_OPTION) $^; \ echo "compile .bin file: $@ OK!" .PHONY: clean clean: $(RM) output/*; \ echo "clean ok!"


https://blog.csdn.net/thisinnocence/article/details/48946645
https://blog.csdn.net/alpha_love/article/details/62953847

Implyment read write lock with mutex

Using two mutexes[edit]

Raynal demonstrates how to implement an R/W lock using two mutexes and a single integer counter. The counter, b, tracks the number of blocking readers. One mutex, r, protects b and is only used by readers; the other, g (for "global") ensures mutual exclusion of writers. This requires that a mutex acquired by one thread can be released by another. The following is pseudocode for the operations:

Begin Read

• Lock r.
• Increment b.
• If b = 1, lock g.
• Unlock r.

End Read

• Lock r.
• Decrement b.
• If b = 0, unlock g.
• Unlock r.

Begin Write

• Lock g.

End Write

• Unlock g.

This implementation is read-preferring.^[

https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock#Using_two_mutexes

Lock Free queue with CAS (compare and swap)

do {
  p = ctx->tail;

  if ( __sync_bool_compare_and_swap(&ctx->tail, p, tmpnode)) {
    p->next=tmpnode;
    break;
  }
} while(1);

First a temporary variable, p, is assigned the same value of the tail of our queue. In this case ctx is short for “queue context”. Next we want to add our new node tmpnode to the end of our queue (make it the tail). If two threads are trying to do this at the same time, then one of them will succeed and one of them will fail. If the compare operation fails then the enqueue action will immediately loop again, trying to do another compare and swap operation, with the updated tail value. It will do this until it is successful, or until the heat death of the universe.

When the compare and set operation is successful, it means that we were able to change the value of the tail. The next line updates the previous tail’s next pointer to point to our new node. We don’t need to do this via a compare and set atomic operation, because if anyone else is trying to modify the the tail, they failed (or otherwise our compare would have failed). The break at the end exits the loop

https://schneems.com/2017/06/28/how-to-write-a-lock-free-queue/

https://www.codeproject.com/Articles/153898/Yet-another-implementation-of-a-lock-free-circular

tmux set mouse mode off for copy/paste

using the command below to turn mouse off for copy/paste

prefix : set -g mouse off

https://stackoverflow.com/questions/17445100/getting-back-old-copy-paste-behaviour-in-tmux-with-mouse

cpp template

cpp template zip file:

google link here

C++ class layout

class layout
https://www.evernote.com/shard/s260/sh/dfc7453b-e50f-46c0-b223-196bead364a9/c41f1cea8f38c1802d1941338b03d375

vtable:
https://en.wikipedia.org/wiki/Virtual_method_table

using CAS to implyment spinlock

#define CAS __sync_bool_compare_and_swap

bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
These builtins perform an atomic compare and swap. That is, if the current value of *ptr is oldval, then write newval into *ptr.The “bool” version returns true if the comparison is successful and newval was written. The “val” version returns the contents of *ptr before the operation. 

static inline void my_spinlock(unsigned int *lock){
    while (!CAS(lock, 0, 1));
}
static inline void my_spinunlock(unsigned int *lock) {
    *lock = 0;
    //CAS(lock, 1, 0);
}

Esxi patch update

Esxi patch update:

esxcli software vib update -d /vmfs/volumes/5a023555-73045df5-66c5-0090fb60192a/ESXi650-201803001.zip

IRQL

What is IRQL and why is it important?

Interrupt Request Levels – aka IRQL’s.  If you develop device drivers or spend a lot of time debugging, IRQL’s are familiar territory for you.  An interrupt request level (IRQL) defines the hardware priority at which a processor operates at any given time. In the Windows Driver Model, a thread running at a low IRQL can be interrupted to run code at a higher IRQL.  The number of IRQL’s and their specific values are processor-dependent.

Processes running at a higher IRQL will pre-empt a thread or interrupt running at a lower IRQL.  An IRQL of 0 means that the processor is running a normal Kernel or User mode process.  An IRQL of 1 means that the processor is running an Asynchronous Procedure Call (APC) or Page Fault.  IRQL 2 is used for deferred procedure calls (DPC) and thread scheduling.  IRQL 2 is known as the DISPATCH_LEVEL.  

When a processor is running at a given IRQL, interrupts at that IRQL and lower are blocked by the processor.  

Therefore, a processor currently at DISPATCH_LEVEL can only be interrupted by a request from an IRQL greater than 2.  A system will schedule all threads to run at IRQL’s below DISPATCH_LEVEL – this level is also where the thread scheduler itself will run.  So if there is a thread that has an IRQL greater than 2, that thread will have exclusive use of the processor.  Since the scheduler runs at DISPATCH_LEVEL, and that interrupt level is now blocked off by the thread at a higher IRQL, the thread scheduler cannot run and schedule any other thread.  So far, this is pretty straightforward – especially when we’re talking about a single processor system.

On a multi-processor system, things get a little complicated.  Since each processor can be running at a different IRQL, you could have a situation where one processor is running a driver routine (Device Interrupt Level – aka DIRQL), while another processor is running driver code at IRQL 0.  Since more than one thread could attempt to access shared data at the same time, drivers should protect the shared data by using some method of synchronization.  Drivers should use a lock that raises the IRQL to the highest level at which any code that could access the data can run.  We’re not going to get too much into Locks and Deadlocks here, but for the sake of our discussion, an example would be a driver using a spin lock to protect data accessible at DISPATCH_LEVEL.  On a single processor system, raising the IRQL to DISPATCH_LEVEL or higher would have the same effect, because the raising of the IRQL prevents the interruption of the code currently executing.

That will actually wrap it up for this post.  It’s a fairly short post, but hopefully you now have a basic understanding of IRQL.  Until next time …

TLS/SSL - handshark

           
              https://training.ti.com/tlsssl-and-https

copy/paste with mouse for tmux on mac

To restore the default copy/paste configuration you need to (at least temporarily) turn off mouse support within tmux:

prefix : set -g mouse off

Where prefix is the tmux access key (Ctrl+B by default unless you re-map it). : starts command mode and set -g sets the parameter globally.

Bash assign variable from a command output

How do I assign the output of a shell command to a shell variable under Unix like operating system? For example, I want to store the date command output to a variable called $now. 

How do you do that?

var=$(/path/to/command arg1 arg2)

The content of test.sh

#!/bin/bash

PROD=$(ls -al)

echo "${PROD}"

the output

~$ bash test.sh |grep xen

drwxrwxr-x   3 user group       4096 Mar  7  2017 test_xen

drwxrwxr-x   3 user group       4096 Mar  7  2017 test_xen_4.7

install cross compiled VIM on the target machine

1. cross compiling vim8.0
2. copy vim to /usr/local/bin on the target machine
3. copy .vimrc to target machine
4. copy syntax.vim to /usr/local/share/vim/syntax on the target machine
5. copy ~/.vim/colors/kolor.vim (kolor is my favorite color theme) to the target machine
6. you are good to go

Migrate KVM Disk Access from IDE to Virtio

So in order to make the switch from from ide or Sata to virtio, the following steps need to be taken:

Run virsh edit <your_vm_name>. From there, edit the config file and adjust all lines of

<target dev='hda' bus='ide'/>

<target dev='sda' bus='sata'/>

so they look like this

<target dev='vda' bus='virtio'/>

Furthermore, remove all <address type .../> lines so that libvirt can regenerate them appropriately.

Inside the guest, edit /etc/fstab and replace all occurrences of /dev/sdX with /dev/vdX`.

That’s it, now shutdown the machine and start it with an virsh start <your_vm_name> (just a reboot inside the started VM won’t work).

using virt-viewer remote access KVM guest vm

sometime you try to access someone's host machine, which KVM running several vm image, you want to access one of the vm.

one the remote host (name: wawr-builder, ip 10.71.50.228) machine: 

wawr@wawr-builder:~$ virsh list

 Id    Name                           State

----------------------------------------------------

 2     Ubuntu64                       running

 11    av_virtual_3                   running

from my local machine, you can do:

jim@jim-dell-5810:~$ virt-viewer --connect qemu+ssh://wawr@10.71.50.228/system av_virtual_3

With the above, you’ll have to enter your SSH password twice – first to establish the connection to the hypervisor and secondly to establish a tunnel to the VM’s VNC/SPICE session

see original post:

https://www.jethrocarr.com/2012/08/04/virt-viewer-remote-access-tricks/

using perf for profiling

the sample code test_a.c as below:

#include <stdio.h>
#include <stdint.h>
#include <string.h>

void func3(void)
{
   int count = 0;
   char src[100];
   char dst[100];
   for(count=0; count < 0XFF; count++)
       memcpy(src,dst, sizeof(src));

   return;
}

void func2()
{
   int count = 0;
   int64_t s =1;
   for(count=0; count < 0XFF; count++)
   {
       s =s *(count+1);
       func3();
   }

   return;
}

void func4()
{
   int count = 0;
   int64_t s =1;
   for(count=0; count < 0XFF; count++)
   {
       s =s *(count+1);
       func3();
   }

   return;
}
void func1(void)
{
   int count = 0;
   for(count=0; count < 0XFFFF; count++)
       func2();

   return;
}

int main(void)
{
    printf("\n Hello World! \n");
    func1();
    printf("\n step 2! \n");
    func4();
    return 0;
}

#compiling with:

gcc -Wall  test_a.c -g -o test_a

#install perf on ubuntu 14:

 sudo apt-get install linux-tools-common linux-tools-generic linux-tools-`uname -r`

#run test_a:

./test_a

#find test_a pid as 21033 through

ps aux|grep test_a

sudo perf record -p 21033

#ctrl+c to break

sudo perf report

it will show the profiling result as below:

now you know the bottle neck--- func3()

you can also see real time cpu usage by :

sudo perf top

other option -g

perf record -g -p pid

perf report -g 'graph,0.5,caller'

perf report --max-stack=6 --stdio -s parent

ref: http://rhaas.blogspot.co.uk/2012/06/perf-good-bad-ugly.html

My git quick start

1. setup git diff tool in ~/.gitconfig

[diff]
    tool = p4merge

You can use git difftool to show a single commit.


Say you want to see the commit with the sha1 abc123:

git difftool abc123~1 abc123



(~1 tells git to move to the previous commit, so abc123~1 is the commit before abc123)


If you use this regularly, you could make a custom git command to make it easier:



Create a file called git-show somewhere on your $PATH with the following contents:
git difftool $1~1 $1



Give that file execute permissions:
chmod +x ~/path/to/git-show



Use the command git-show <sha1 or tag or ...>                                                           




For the modified files on current branch:


   git difftool ./my_modified_file



After git add command (staged files)
   git difftool --staged


2. git show current branch name:


   git branch






3. git show all remote branches:


  git branch --all






4. git switch branch:



  git checkout my_branch_name



5. git Add file:

  git add ./path/my_file.txt



6. git commit changes:

  git commit -m "my change text"



7. git push

  git push



8. git log, show change history

  git log



9. delete remote branch

  git push origin --delete branch_name



10. branch diff

   git diff master_git master_git_test



11. Create a local branch test which will use to track remote branch origin/test:

    git branch test origin/test