Service Directory Insertion Order: Fill & Download for Free

Yes, with a pretty big caveat.I generally get to understand the problem to the point where I know what algorithm or combination of algorithms I will need to solve the problem. If I have a huge amount of data, whether I can go to storage or fit it all in memory, the insertion order, the insertion rate, the graph dependencies, and so forth.This also gives me information on whether a canned version of an algorithm is capable of solving the problem, or whether it's going to need a variant, and if it needs a variant, what the impact will be on the algorithm, and so forth.EXAMPLE 1Say I'm going to insert an arbitrary amount of data, the data insertion has to be O(1), the lookup is allowed to be O(log2(N)), duplicate insertions are an input error, and it's too much data to fit into memory at once, so I'm definitely going to be hitting slower-than-RAM-storage. There are no other constraints.This probably means that I'm going to want to use an infix tree. This is kind of an oddball algorithm that you don't find in many books, and if you Google'd for it, your going to find the Solaris per process open file table implementation, and not a lot else, and in the comments at the top, you're going to see that it's patented with some pretty specific claims, and, further, the code is under the SCSL.And you really can't un-see the patent claim.But as I said, the claims are pretty specific, and it doesn't take a lot of thinking, and it's actually relatively easy to wiggle out from under the patent.So you ignore the Sun code, and you write your own implementation that doesn't infringe the patent.That's a case where I've used GoogleI didn't use the code I found as a result of GoogleAnd I built an implementation were Sun/Oracle is not going to come after me later over the patentEXAMPLE 2I'm going to be getting a bunch of work items that have an expiration time set at some point in the future, but I know that most of them will be asynchronously removed before they expire, so most of the time, I'm not looking at them myself, because some work-item-has-already-been-serviced routine is going to reach in and remove the item. Further, the unit time is always at a constant distance into the future, and I don't want to have to iterate all the items in order to deal with it.So... my insertion time needs to be O(1), my removal time is less important, but let's say since the caller might care, I want the removal time to be O(1) as well, and let's say that I want the expiration traversal to be O(n), but I'm willing to live with O(n+1), where N is the number of items, and n is the number of items expiring in any given timeout interval.In case you don't recognize this, this is the 2MSL TCP retransmit timeout for unacknowledged data packets within a sliding network window.For the timer, I choose to use a circle queue with a fixed number of items (in order to use a perfect hash, I'm going to want to use a power of 2 for this), and I hash to select the queue element to put the work item in, and I'll use a hash chain whose head is the circle queue element item, and then for the hash chain itself, since something can asynchronously reach into the entire storage structure to remove items, I'm going to use a linked list (as opposed to the tail queue or singly linked list that I might use, if all the items were going to stay in place until they expire (gotta remove the retransmit work element if the data was ACK'ed, after all, instead of sending it again).Fortunately, I know that there is a circle queue implementation in <queue.h>, and that there's a doubly linked list implementation in <queue.h>, and I can do a perfect hash using modular arithmetic or a simple bit mask AND, if I made it a power of two to begin with (which I did).The only other pieces I need are a clock pointer that's a hash list head pointer into the current head item in the circle queue (and I "tick" the clock by traversing to the next item in the work queue), and the insertion, traverse-and-remove routine and the async remove routine.The async remove is already written; there's a remove function in the LIST implementation; the traversal is also written, it's FOREACH_SAFE (since I may be removing the item, and I want an efficiency, so I can't use FOREACH).So I...InsertHash to find the bucket in the circle queueInsert items at the tail (they time out later than all other items already inserted anyway)Early removeJust use the TAILQ_REMOVE; the socket structure point to this alreadyTick forward and expireTraverse the "tick" pointer forwardLIST_FOREACH_SAFE to traverse forwardIf the item is expired, expire itIf the item is not expired, then I'm done with this tick, and early exit the loop -- this is the (n + 1)th itemI've just implemented the TCP retransmit timer code, and I've done it using code that I already knew was on my system:This is a case I can solve without having to Google anything, because I only used code that was already thereEXAMPLE 3I'm implementing SIX (Shared, Intention eXclusive) in a lock manager, because it has to be incredibly concurrent, I don't want to have to deal with head of line blocking, I don't want to have to deal with starvation deadlock, and I don't want to have to deal with what Jeff Mogul of DEC Western Research Labs called "receiver livelock (for example, I'd get that if I was granting new Shared lock while there was an eXclusive lock pending).I can do most of this myself. However... I know that any thread of execution that comes in is going to need to potentially grab two locks.For example: I'm implementing a kernel thread reentrant safe version of the UFS filesystem, and I may have to deal with two directory entry blocks (device blocks, because that's how UFS implements its directory entries) that need to be written simultaneously, while guarding against other readers and writers. This is because a RENAME operation is a "find an empty directory entry slot in the target, hard link the old inode into the new directory, and then DELETE the old directory inode reference (unlink it there).NB: One of the reasons that Mac OS X deprecated UFS as a filesystem is that the in core inode for the directory vnode is used to store this information, and you can crash the system if you allow file system reentrancy, but Mac OS X wanted to support kernel reentrancy on multiprocessor systems.So I decided SIX locks fit the bill for highest possible concurrency, since most operations on a file system are operations on an existing file, creates, or deletes, but renames have to be supported.Now I'm in trouble: to implement this correctly, I have to use a DAG (Directed Acyclic Graph) of the lock nodes along the file system hierarchies in question. I take S locks from the root to the terminal directory, then take an X lock on the directory (or directories, if it's being renamed elsewhere, rather than in place). Then I do the rename, then I release the X lock (X locks are also held on create operations; everything else uses S locks, because they are only looking things up).NB: This situation arises because rename operations are not atomic, but they must be idempotent, or your filesystem is not POSIX compliant, and it's impossible to implement a reliable database operation, temporary save files (e.g. in a word processor) and so on.I need Warshall's algorithm, so that I can check that no two paired X nodes already inserted into the graph are not bifurcated by the two X nodes I want to insert into the graph (e.g.: conflicting rename operations operating on the same directory entry block).THIS, I Google!Why?I rarely use Warshall's algorithm; it's not often I need to compute transitive closure over a DAG (Directed Acyclic Graph) with two subsegments with an implied cyclic edge (two locks are being held in different places)It's really, really easy to screw up (trust me); infinite loops in filesystems are NOT pretty! Even if you happen to have a copy of Sedgewick's Algorithms in C++ in your hand, and happen to know it's described in the "advanced topics" section at the end of the book, that's not the same as writing it correctly.I can find some code for this rather complex thing that someone has already written -- and debuggedI don't need the headache(!)So yeah, you use Google, but that doesn't mean you can use the code you find, and there are certain things that you should "just know" at some point in your career, without having to use Google to find them, but when you need it, you need it.These are all just hypothetical case examples I made up off the top of my head. I probably would tweak several of them.For example, I'd probably build transitive closure calculations incrementally into my X lock assertion routine; I know I can do this because it's a DAG, and all I have to do is traverse both nosed to the root, and then traverse that segment as a new graph to look for conflicting segments. If it were actually cyclic, rather than virtually cyclic, I wouldn't be able to do this.Yes, I realize that that's a pretty big caveat; and that I cheated by knowing about <queue.h>, rather than having to Google to find it (but is that cheating, if you're a "top engineer"? I'd say no...).Google is fine when you need it, but a "top engineer" should probably know their stuff well enough that they don't need it.Knowing that someone can probably use Google to find the solution to a problem is really no excuse for not just knowing the solution to the problem -- even if you end up taking a corpus of already written code from a system header file, or a system library, or someone's implementation out there in the Google-sphere.

The hardware isn’t really there for what I’d want to do most, which is to remove the protection domain crossing overhead by engaging in statistical memory protection.This is actually a relatively easy thing to do, if you had a 128 bit address space, and substantially less physical memoryMost systems can address 53–56 bits of physical RAM, depending on the system, so 64 bits is not enough to eliminate the hardware protection domain and replace it with a fatal page miss fault.So that’s off the table.After that, I’d make all call gates asynchronous instead of synchronous, with an ability to specify a wait, which you’d do by not passing the address of a completion routine to be called back into user space on a synthetic thread in order to deal with system call completion.This would also have the effect that you would need to eliminate all user kernel boundary crossings and library routines which were not inherently thread or signal safe.One major thing I’d do is get rid of envp; I think environment variables need to be hung off the proc struct, and live in kernel space. Local environment variables attached to the current process should be consulted first, and in the event of a miss, then environment variables associated with the process group, and after that, environment variables associated with the “init” process, or whatever passes for the init process (on Linux, this would be “systemd”; on “macOS, this would be “launchd”.Getting rid of the data interface to the environment, and replacing it with a procedural interface fixes a huge number of things, including providing separate process, group, and system logical name tables in place of a flat environment namespace, and enables things like variant symbolic links.Globbing would not be in user space.Although a lot of aspects of the UNIX shells are based on having globbing expanded in user space and passed as arguments, it’s possible to provide that same functionality by having the kernel interpret the globbing, and pass back a list in the same way that the readdir() function operates to return file names; you’d merely apply a globbing filter.By putting globbing in the kernel, you can support an auxiliary namespace, which would then permit supporting versioning directly in the filesystem, with implied “most recent version, if you don’t insert the semantic overrides in-band in the file name resolution interfaces.So those are three major revisions I think need to happen.Per thread current working directories would also be usedful.One of the Abominations Before God which has been added in the name of HPC (High Performance Computing) is that every function which takes a file name, and thus can resolve the file name relative to the current working directory, now also has a version that takes an fd as a directory handle instead.So for open(), there is openat(), for stat(), there’s statat(), etc..All of this additional parameter passing is both useless and wasteful of CPU cycles, when you could, for example, just tell a web server that its worker thread pool threads had a current working directory — or even a per thread chroot() directory — of the web server’s CGI directory.If you want compatibility, it can be accomplished idempotently by setting the per thread current working directory, making the non “at” version of the call, and then (if necessary) clearing the per thread current working directory.It is, however, far more likely that you’d simply lazy-bind the setting of the per thread current working directory, and only modify it when the kernel space version of the thread, and the user space TLS version of the fd for the the directory you want as your working directory, only calls the set call if they differ.Which in any HPC application, they never will, and in any work-to-do thread model will only apply to multihomed servers, and even then, will only apply if they are seeing something other than flash crowds (in which case the overhead will be capable of being eaten without a significant latency anyway).And that’s just the simple stuff.We haven’t even talked about what needs done to the network stack.For example — if you are watching a Netflix movie … do you really give a flying crap where the next 6000 frames come from, so long as they are there before you need to render, and then display them?Why connect to a server, rather than a service?TCP/IP needs a major makeover for distributed cluster computing with persistent connections to services, rather than specific server hardware.Throw in TCP rate halving for congestion, and LRP (Lazy Receiver Processing) for livelock —- sorry, your ethernet card firmware will need to change for that one — and then you are looking to VRRP (Virtual Router Redundancy Protocol) based handoff to other service provision points, and running with one armed load balancers and TCP half splices ()only necessary until the TCP/IP fix is in).Speaking of which… SYN/SYN-ACK/ACK has to go (syn flooding) and so does FIN-WAIT-2 (dangling close flooding) to fix the most vulnerable parts of the protocol stack.Oh. Also: do not get me started on the UDP packet fragment reassembly buffer, which I can use to kill most Linux machines by sending N-1 UDP frags for a bunch of oversized UDP packets, just to screw with the mbuf count on the host.P.S.: Lying about remaining window size to the router? Yeah, that’s a thing for QoS, which works a hell of a lot better than “packet shaping” to not use up all an intermediate routers buffers, especially when there’s a differential on internal and external WAN port throughput and/or latency.Beats the every loving snot out of RED queuing.And that?That’s just a fraction of the simple kernel architecture work, before you put anything on top of it.You have a couple of decades, or a couple of hundred good kernel hackers? Find funding for it, and we can maybe talk.

IMHO - Start with the man command.Then check out Compiz and Emerald, wait that..... (joke)Where was I.... Sorry, by using man or man pages we can quickly learn about the commands. Man pages are a (manual for almost everything) so why don't we start with:man man ##and then man ls ##and then man ps ##and then man top ##and man lsof ##and man cat ##or man find ##then definitely man grep ##commands You'll also want to get familiar with 'apropos' - it's kind of 'grep' for the man pages.That’s just for starters, these commands are your eyes, ears, nose, hands, legs and arms always be ready to insert your man prefix before running a command or before wishing you were better at running said command. .After a while instead of man you may decide it in your best interest to just:"insert command" -h or “insert command” --help (but not “insert command” /help) Vim is your command line editor (unless you're an emacs kinda guy/gal) and it stands for very improved vi, which is what Vim used to be and still is (if you use Solaris for instance). If you use vi or vim use the view command for everything and then vim or vi only when you mean to actually edit a file (can be VERY IMPORTANT if you're in production as view will not let you save a file with any write operation.)So you'll need to know that you press ctl + the up arrow, or down arrow to page up and down. You type in a / to search below your cursor in said file or files for string-literal or you may decide to ? search above said cursor in said file. You might know that what you are looking for is at the bottom of the 20 meg text file so in that case you don't want to page through them all so you just shift g and you'll be at the bottom, and once you get there, you might decide that you forgot to copy a line of text which was on line 1 of the document, in that case you want to type the number 1 on your keyboard, followed by shift & g.Also learn about your hardware through the eyes of Linuxview /proc/cpuinfo cat /proc/meminfo head -5000 /proc/zoneinfo tail -f /proc/mounts Learn all of the directories and what they are for (at least the ones which live on your "root" directory or "/" which is the same as C:\ or D:\ or $WINNT or $SYSTEM32 or whatever it is these days.So /etc is usually where your server config directories and files live in posix (standard for UNIX and Linux)I suppose you're going to keep developing Java, but if notman pythonMoving on... ....you'll want to get comfortable with Tomcat I'm sure. First you will want to install the Java SDK so you will need to learn two of the coolest Linux commands (these both work only for Debian flavors of Linux like Ubuntu, Debian and a million others (but not Suse or RedHat or Oracle RHEL for instance, I think it is called invincible Linux now.)Sudo (do something as the superuser (almost root) but then resort to a plain Jane account (good idea)).Sosudo -h or  man sudo  then you will learn that some commands need sudo especially if you need to run a DNS server (sudo nobody) or sudo postgres and so on. (you rarely have to do this outside of custom configuration)So now every Ubuntu enthusiasts favorite apt-get --supercow (joking apt-get doesn't have super cow powers) butman apt ##and  man apt-get ##and  man apt-cache ##and learn which and what is appropriate.  So I think you can apt-get update (this will download the latest and greatest links to the latest and greatest packages) and then apt-get search or perhaps you have to apt-cache search (for offline cache usage) then after the search command type in java and after you realize the HUGE amount of stuff with java in it refine your search after learning how to use the name predicate so that only packages with Java in the name return.There is also a GUI that does all the same things in the main menu but I can not stress enough how important and how much more productive everything is with POSIX bash and command line and perl and my personal favorite Python.You might want to deck your distro out at this point, just keep in mind you should always be security conscious--viruses are much more common on Linux these days as a partial result of OS X popularity. You should uninstall software you won't use is all I mean by that you don't want 10 servers running on every span of 100 ports.But by all means learn to:"apt-get install go-go-gadget-super-cow-ninjas"apt-get install update  ##to download security and bug fixes and then  apt-get install dist-upgrade  if you really want to live on the edge.apt-get install firefox or apt-get install mysql ##or apt-get install hadoop ##or apt-get install cassandra ##or apt-get install postgres ##or apt-get install postgis  I think you get the point, the world is now in your hands, you are using Linux, and don't forget to become a registered user of the kernel and your favorite distros. You now are a message away from some of the most intelligent, selfless, friendly, and totally hilarious and backwards people!If you turn into a real Linux guru, you'll most likely trade in your apt-get for make-git err... I mean your apt to make and git yer own softwares without the use of said package manager. Anyhowmake -h ##or man make ##then git -h ##but definitely  man git Oh Tomcat!ls -latrh |grep /etc/tom You will probably see some tomcat stuff here.Also you can echo $ENV or ./env if my memory serves me correct.plusecho $EXTRA_JAVA_OPTS  echo $JAVA_OPTS If you are from Windows those are like your system variables. You can do a lot of damage by messing these up so back up your $ENV output before messing around (you shouldn't have to change things as a rule until you are ready to customize a development or production system.)/etc/init.d/tomcat restartor/sbin/service tomcat5 -h  moving on....ls -latrh  # (-abc = -a -b -c sometimes) # (-a for hidden -h for human output) # # are for comments.  ps -eafxh ps is a great command, it will let you learn about processes and when they were ran, and who ran them, from where, perhaps why.nmapnmap -h nmap is a network lightsaber or tool to help you learn about the port-a-verse. Scan only your local server for open ports. Start with only your local host and create a virtual machine you don't care about on 192.168.1.x or whatever if you really want to learn because you can do some really cool stuff, do not scan machines that are not yours without first:Knowing what you are doing andSome people think permission is nice so not a bad idea to not scan what is not yours although people will disagree with this.lsof -v |grep try_searching_herelsof will list open files, network connections, ports, exedra...ntop -h network status top command, protocols UDP, TCP, DNS, HTTP, resource usage of networksvmstat -h(virtual stats)Alsoiptables -h pf -h iptables are your firewall or pf (which is the new standard in firewalls.)also don’t forgetopensnoop -f /blah/blah/blah.blah (snoop on a directory or file or process or pattern)iotop -h (input output heavy procs listed in order of IO consumption.)tcpdump -vv -w /write-it-to-a-file.pcap ## while that is running in one window tcpdump -vv -r /where-you-wrote-your-file/what-you-named-your-file.pcap tcpdump is one of my favorites, you learn more about this command and in turn it teaches you more and more about networking protocols, and what types of things happen on which network layers and so forth.Give me some thumbs up and I'll refine more, I really hope that helps someone! Good luck feel free to ask me anything.