Veritas Interview Part I

This is bloody cool .. believe me ... And this time i didnt have to use "Towers of Honoi" Trick

Interview -

Q1: So you have worked with filesystems, tell me about the work.
Ans: I have just sent out patches for Unionfs, a vfs-layer fanout file-system. But thats my hobby My work at Ensim is in system level.

Q2. What entry points into the VFS you would have to trap, to handle this situation.
And: Everything including open, create, readdir .. etc. The only execeptions are sendfile and mmap and some others.

Q3. Can't you just pass the lower level dentries to mounted filesystem.
And: Its a union so you have to union directory entries hence create new interposed inodes and dentries. And Also coz you have to maintain different caches at different levels. The the files you craete/delete over the union are not there on the lower branches. And you don't want writes to the lower branches to affect the union.

Q4. What could be the implecations of nfs over unionfs. Tell me how mmap works over NFS.
Ans: mmap i am not sure, But in general NFS relies upon persistant inodes. i.e the inode numbers should be same over remounts. Since unionfs creates vnodes on the fly it can't ensure same inode numbers over the remounts. Although I had thought of a patch for computing inode numbers as a hash of the file path. but it would be a problem for hardlinks.

Q5. How would you write a disk defragment software for ext3. Are there any benifits in doing that.
Ans: It would be good for any filesystem to have disk defragmentation as it brings all the file blocks together. It saves -
1. reading time
2. inode table space. As inodes would not be dublicated over multiple inode blocks.

Algo:
1. Lock superblock
2. Aquire semaphore over inode.
2. Everytime you move the blocks ensure that file cache is distoyed. This can be done by increasing the superblock generation number. or otherwise...
3. Update inode tables
4. Release locks.

Q6. How does a fs say ext3 serializes the read/write on same byte over same file.
Ans: In uniprocessor it already serialized. In SMP I guess the bus controller ensures that. I think so ....

Q7. Whats the difference between Semaphores and Spin Locks ?
Semaphores sleep while waiting. Spin locks spin in a while(1) loop. Spin locks make no sence in uniprocessor as there is only on thread running.

In SMP .. you cant implement semaphores without using spin locks. In SMP data-structure of semaphore itself becomes a critical section. ..You have to ensure local interupts are disabled and SMP waits over spin lock.

There is an overhead in semaphores of acquiring a spin lock and then enqueuing the task struct and the dequeuing it. Better use a spin lock if you know wait would not be much.

Q8. In which parts of the kernel code you can't use semaphores.
Ans: Interrupt handlers. They obviously can't sleep over locks.

Q9. In SMP environment would the CPU cache cause a problem in spin locks. How would you avoid it.
Ans: Cache in L1/L2 may become dirty in one CPU. So other CPU must be informed about it. x86 uses interprocessor interrupts to flush the cache. I think c0 control register is used for it.

Typical use case is after using a spinlock. The spinning condition is almost always in cache and a spinlock changes the value for which the other CPU is waiting/spinning for.

Q10. How would you make sure the instructions are serialized and there is no optimization by the compiler/CPU over the instructions.
Ans: Use something called memory barriers. In x86 use a prefix instruction called "lock". Which requests the CPU to do all thats written before this point before executing the instruction.

In compiler you could append volatile before asm qualifier.


Q11. How do you insure such things in C. Give me an example of a possible scenario.
Ans: Same volatile. Typical use case is when a global variable changes in signal handler. If that variable doesn't directly change in the function. The compiler makes it constant i.e reads the variable value from the memory and copies to the DS (Data segment) and never refers back to the changed value.

Putting a volatile qualifier tells gcc not to make such assumptions.

Q12. Do you know about itanium architechture? In a project in veritas, We had problems with spin locks over different itanium CPUs in same machine. One lock was increasing the value and the other decreasing the value. How would you avoid race conditions in this case. Are there any instructions x86/ia64 insures for this.
Ans: x86 gives atomic instructions to test_and_set the value in the memory. I guess BTS, BTC inctrutions can work well over SMP... and also those 'X' instruction for byte manipulation like CMPXCHG etc.

Q13. How POSIX recomends locks in system level. Tell me the rules.
Ans: Posix recomends mandatory and advisory locks. In mandatory locks every system call has to wait for a lock (if it is acquired). Generally syscall send a signal to the lock owner and waits for a lease time. After that they forcefully take the lock.

Q14. Explain segmentation in Linux wrt to x86.
Ans: Linux doesn't use segmentation of x86. The 16 segment selectors (DS,SS, ES) all point to GDT tables with have initialized the segment descripter with base addreess as 0x0000

Q15. Explain paging with respect to x86.
Ans: Explained.

Q16. Can I do everything in software or hardware support is necessary.
Ans: Everything but the page cache misses. (Answered after a lot of struggle)

Q17. We wanted to have more than 8KB serialized physical memory allocation for a process in Linux. Is it easy/difficult.
Ans: Sorry :D


Q18. I have a machine with infinite RAM. Do i still near virtual memory.
Ans: Yes, to have on demand pagging.

Q19. And if don't i want on demand fecthing.
Ans: When you would have to statically compile all the code. There would be no dinamic compilation.

Q20. Have you heard about. Paging extentions in x86 (P4 onwards). Explain.
Ans: Fortunately yes. You basically use a PDTR to address 64 GB of ram with page size as 2MB. P4 gives 36 address lines inspite of 32 in normal case.

Q21. Will that have good bad effect on TLB hits.
Ans: (With lots of struggle) TLB will improve as it can adress moe mem.

Q22. I have an adjacency list of a graph. And for each node i want to sort the neighbours.
1 -> 5 , 3 , 2
2 -> 1, 4, 3
3 -> 2 , 1 , 5

becomes ..
1-> 2, 3, 5
2 -> 1, 3, 4
3-> 1, 2, 5
Solve.

Ans: (With lotz of struggle) After sorting the first list you can make out that if
1-> 2, 3, 5 then all 2,3,&5 will have first element as 1. And so on.


Q23. I have overlapping line segments and then i give you a point. You gotto tell me how many lines would have this point.

Ans: Used R-trees ( the guy gave some hints )


Just waiting for results now .... :D