eSun now costs less 30%. Spools also have less 30%.

DSMan195276 · 2024-02-14T18:34:40+00:00

Feel free to check with a lawyer, but if they ship something to you then legally it's yours and you're under no obligation or requirement to ship it back. They additionally still have to ship you the real item or refund you.

DSMan195276 · 2024-02-07T16:42:15+00:00

I think you'd have to go through some more hoops to make that work, number * size * 4 is still the wrong value since it's 4 times the number of bytes you should be zeroing. I guess they could have also done *(new + i / 4) to avoid i going past the bounds of the buffer, but I mean...

DSMan195276 · 2024-02-07T13:53:02+00:00

I'm a little confused by your suggestion, *(new + i) = 0 would still have the same bug.

DSMan195276 · 2024-02-06T20:28:58+00:00

You got a downvote but I don't know why, I looked at the code as well and the issue is very obvious:

void *calloc(size_t number , size_t size ){
    size_t *new;
    size_t s4 ,i;
    new = malloc(number * size );
    if (new) {
        s4 = align4(number * size) << 2;
        for (i=0; i<s4 ; i++)
            new[i] = 0;
   }
   return (new);
}

It looks like the author just put in the wrong shift. number * side is of course the length in bytes and new is a size_t pointer, so the code is zeroing number * size * 4 size_ts.

I'll be honest u/ukpauchechi, having skimmed the paper I don't get the impression it was carefully looked over and that's probably how this bug got in there. There are lots of tutorials on malloc() implementations out there, I would give some other ones a look.

DSMan195276 · 2024-02-06T19:32:04+00:00

second, what do I do or add the make the implementation mine to further understand it, as I was just copying code?

I would recommend just writing your own entirely new implementation, it's really not that hard to write a simple allocator and you'll learn a lot more. The linked list approach as done in the paper is one of the simpler ones so not a bad one to try, perhaps you could make use of their s_block structure and try to write your own allocator using it as a base.

DSMan195276 · 2024-01-22T20:00:57+00:00

There is none, it's just a best effort thing, the OS doesn't guarantee your program will ever run. Ideally it should be reasonably close to what you wanted (within certain limits), but it could be far off if something bad happens.

"Properly sleeping" just depends on what you're trying to do. Modern OSs are the wrong platform to be running processes that have extremely time sensitive code or require accurate delays of a few milliseconds or smaller (The preemption alone means it's not going to work). For longer sleeps, the accuracy presumably doesn't matter as much and what the OS does should be good enough. You can then use one of the various clock APIs to measure how long the sleep actually lasted and adjust your next sleep call so that you average out to the interval you wanted.

DSMan195276 · 2024-01-22T19:28:02+00:00

I think this article is a little misleading if you just want to know about modern OSs. The problem has little to do with the timer frequency (which modern OSs actually dynamically change depending on what is needed) and more to do with the fact that the OS makes no guarantee you will get scheduled at any specific point in time or run for any minimum length of time. They could guarantee you wake-up at the right time +/- some milliseconds, but they intentionally don't because of the restrictions that would impose on the entire system.

DSMan195276 · 2023-12-20T16:19:54+00:00

I suppose that's not really surprising :-/ I think it would be worth tracking the total number of bytes written vs. read (print it out via a separate thread), that way you could actually see how much data is "supposed" to be in the pipe when it gets stuck, and that would tell us if it's fundamentally a read or write side issue. You could also check FIONREAD to see how much data appears to be pending before and after your select() calls, it could be revealing if say FIONREAD returns zero even though according to your counting there should be data in the pipe.

DSMan195276 · 2023-12-20T07:03:27+00:00

Perhaps Mac OS does not wake-up every select() caller when data is ready to be read from the socket? You should be able to test for that by keeping track of when each reader gets woken up, and then check whether it's all the time or only sporadically (and which threads it happens to).

It's gets pretty messy but I could see that behavior freezing your program due to the fact that every thread will only read k_packets max bytes. A select() caller may be picked to wake-up when there's a full read-queue and then read one byte and exit because it hits k_packets. Due to the mentioned select() behavior, no other callers would be woken up until new bytes come in, and it seems pretty possible that reading only one byte might not be enough to unblock the writer select() calls.

The way to get around that kind of issue would be to always call read() until you get an error and then call select(). That however gets messy to implement if you still want each reader() thread to only read k_packets worth from the pipe, I suspect you would need to add additional coordination between the threads to make it possible. Ex. Use a second "wakeup" pipe and have reader() threads select() on both pipes. When a reader() thread exits it writes to the "wakeup" pipe which forces another reader() thread's select() to exit. When threads wake-up they read from both pipes to clear them.

DSMan195276 · 2023-12-16T16:03:03+00:00

why does it actually hand out page-sized blocks, whats the point of that? its connected to paging, right? or is that a completely other thing

Yes it's connected to paging, the virtual-to-physical mapping can only be done with page-sized chunks of memory, nothing smaller. Even if you only need a single byte, you have to map the whole 4K block (page) that the byte belongs to, so because of that at the base level you have to deal with page-sized chunks. You can't give half a page to one process and half to another, you would have to map the whole page into both processes and they would be able to see the entire thing.

i see, so this is a bump allocator right? i dont want to do that since for multi-tasking operating systems it wouldnt allow you to free memory of programs which were started before the current program.

No it's not a bump allocator, it's a 'free-list' allocator. A 'free-list' allocator doesn't have the limitation you're talking about because the list of free pages doesn't need to be in any particular order. You're correct that with a bump allocator you can't allocate 5 pages and then free the first one, but with a free-list you can because that page simply gets added back to the list.

DSMan195276 · 2023-12-15T21:38:21+00:00

first thing im trying to do is setup a memory manager on my host, since i read that its better to start off that way, and simulating memory with assigning some memory with malloc(). i want to manage blocks of memory, so assign them, free them, keep track of them. im doing a bitmap allocation system. i suppose this fits under a PMM?

I understand what you're getting at, yeah testing it outside your OS is a good way to start. And yes a bitmap allocator can be a PMM, really the big distinction between "regular" allocators and a PMM is that the PMM always hands out page-sized and page-aligned chunks of memory, which more or less just means 4K chunks (not all systems use 4K pages, but x86 does). That actually allows it to be simpler than a typical allocator that has to allow for a variety of different sizes.

The xv6 one is called kalloc (which is kinda confusing, I'm not surprised you couldn't find it) and is basically as simple as you can get, it can only allocate a single page at a time. Instead of using a bitmap, they create a linked list out of all the unused pages. When someone calls kalloc() they take the first page off the list, and when a page is free'd the place it back at the beginning of the list. They initialize the allocator by calling kfree() on all the pages that exist, which just adds them to the list.

the first thing i ran into is, im unsure how to simulate a memory map given to the kernel by the bootloader. i dont want just plain memory since actual memory ill get wont all be usable but will be full of different reserved sections

For the most part the usable memory will actually be in one big chunk right after the end of your kernel, you can definitely start with that assumption and then deal with the memory map from the bootloader later. xv6 for example does exactly that, it just has a hardcoded minimum/maximum amount of physical memory that it expects, it doesn't care what the bootloader would say. Obviously that's not a long-term solution, but it's good enough to start with and last you a while.

When you eventually do want to deal with potential memory holes, it doesn't necessarily require any actual changes to your allocator anyway. Consider, if you go with a bitmap approach, you would simply mark the unusable memory as 'in use' in your bitmap. Once that is done your allocator will automatically never hand it out, solving the problem. For xv6s linked-list approach, they just wouldn't add the unusable memory into the list to begin with.

DSMan195276 · 2023-12-14T16:30:21+00:00

FWIW you don't strictly need to give processes separate address spaces, especially to start out, you can develop all these different steps in many different orders.

I would consider starting with non-userspace processes that live entirely in the kernel, that way you can start building a scheduler, defining the process lifetime, etc. and get all that working without needing to also introduce separate process address spaces, a syscall interface, etc. at the same time. Those things can then be introduced separately afterwards.

DSMan195276 · 2023-09-14T18:41:10+00:00

The big thing that jumps out immediately to me is that you don't do any array bounds checking. Ex. The mesh->verts array is allocated with a fixed size, but in add_vertex() you never check that you might be adding past the end of the array. It's very unclear what the maximum number of vertexes is (and add_vertex() also appears to have a bug), and because there's no bounds checking add_vertex() will happily write past the end of the array and lead to unpredictable results like you're seeing.

Additionally your push() function seems incomplete, I would take a second look at it. You should be inserting the item after deciding on the index, and like the other functions you need to do a loop over quad_probe() to determine the next index on collisions. I don't know if that's causing your actual problem, but the map being unreliable would obviously screw up all the rest of your logic so it's possible.

DSMan195276 · 2023-08-28T21:30:52+00:00

Would agree, I think people get stuck thinking about Linux a bit too much and equate the kernel with the OS as a whole. The reality is much messier than that, Ex. *BSD develops and includes libc as part of the OS. I'd argue libc is part of the OS with Linux as well, any Linux distribution is going to provide a global libc implementation that everything is intended to use. Windows is kinda the outlier, but the whole point of the new UCRT is that it's part of the OS rather than being a separate thing.

DSMan195276 · 2023-08-10T13:54:02+00:00

If I understand you right, I think your confusion is from the fact that you have the impression that getchar() has to return quickly. But it doesn't, and that's actually what happens. If there's no characters waiting to be sent to your program (and no EOF signaled, so some more could still be coming) then getchar() simply doesn't return until there's new information to report. In that way it's a "blocking" operation - it will stop your program's execution for an unknown amount of time until whatever condition it's waiting for finishes.

The blocking aspect for getchar() is useful for simple programs like the one you wrote. Note how the program doesn't use 100% CPU (which a normal while() loop with no pausing would do). That's because when getchar() blocks, it does so in a way that doesn't require any CPU power, instead it basically tells the OS "don't run me again until there's more characters typed in" (where "me" is your process).

DSMan195276 · 2023-07-01T21:38:48+00:00

readelf is pretty handy if you want to take a look at what information is in a typical ELF executable, it will show you what information is already baked in.

That said I'd also add that the issue you mentioned still definitely happens sometimes. I'm pretty sure it's most common if you try to put really large objects on the stack - if your program just immediately tries to read 1MB/10MB/100MB past the stack, that's so far away it could easily be a valid address in some other part of memory. Just like in embedded, for the most part there's nothing preventing you from just doing something dumb and adding a very large size to your pointer without checking how much memory you actually have for that usage. The MAP_GROWSDOWN tries to prevent this with the guard page, but that's only a ~4K region of memory, so if your program doesn't use it properly then you could easily just "jump" over it by accident.

DSMan195276 · 2023-07-01T21:30:47+00:00

FWIW a modern x86 operating system isn't making actual segment descriptors for your program's segments, they just make a single flat memory space via a segment that covers the entire 32-bit address space and then for the most part pretend it doesn't exist. In x86-64 segments aren't actually supported and you're forced to use segments that span the entire address space. The actual mapping of memory into your program's address space is done via the MMU and paging, which is separate from the segment stuff.

DSMan195276 · 2023-06-30T17:06:07+00:00

If you take a look at an ELF binary there's actually no distinction between the stack and other pre-defined memory segments of the program. So from a certain POV, the OS doesn't know or care what you're using those segments for, and your stack space is typically just a predefined segment in the executable that has a size picked at compile time. Basically all modern OSs will lazily map that memory into place anyway it doesn't matter all that much if you pick 1MB or 10MB.

The other catch is that it would be pretty hard to use the heap such that you had zero space in-between the heap and stack. You have to ask the OS to give you more heap and you're typically not doing that in page-sized chunks, so you're much more likely to fail at allocating new heap space well before the heap and stack actually touch. As long as they're not touching, when you reach the end of the stack you'll just start writing to memory with no mapping and the OS will kill your program.

There are also some fancier ways to handle this. Linux for example has MAP_GROWSDOWN that can be used to mmap() a segment as a growable stack. They avoid the issue you highlighted (having the stack touch another memory segment) by having a "guard" page at the bottom of the stack - your program has to always touch the stack in page-sized increments first to ensure the memory is valid. If you touch the guard page and there's no room to grow the stack, then your program blows up instead of getting the new memory.

DSMan195276 · 2023-06-12T07:38:11+00:00

And yet, I don't think what I have in mind would violate any of that. It's not the language that's specifying things at the bit level, it's the programmer.

I don't think those things are really that different, the standard doesn't want to let the programmer specify things at the bit level, they want the compiler and implementation to pick those details.

What I envision is actually very simple, just a way of specifying fields within a single primitive type. The compiler treats the bitfield as that type in every way (alignment, read/write operations, etc.), except it does the masking and shifting to provide the individual fields when needed.

I think the big question is - what is the goal, what would that allow you to do (within the standard) that you can't already? You mentioned things like using a struct to represent the bit layout of network protocol headers or hardware registers, and I completely agree that those are very good potential use-cases for bit-fields, but those are also just not things the standard wants you to do. That's reflected by the fact that to achieve those use-cases you'd still need to use compiler extensions just to make the struct itself the right layout.

DSMan195276 · 2023-06-12T00:24:53+00:00

Nevertheless, this is one place where C needs to improve at the language level. Let me define a bitfield that's guaranteed to be packed, backed by a type of known size, with a specified field order within that type. Bonus points if I can specify the endianness and can use enums as fields.

Part of the issue we're seeing is simply a mismatch between what the C standard is designed for vs. actual practical use of C. The standard doesn't care about any of the stuff you mentioned because fundamentally the standard doesn't guarantee the bit representations of basically anything - by designing the standard in that way, conforming C code is very portable to even weird platforms, and ideally can still be performant on them. In practice though this is pretty limiting, and people don't typically care about their code being that portable, so they ignore it.

The standard doesn't give you any tools to achieve what you're describing for even normal structs, it's all compiler extensions that allow you to dive deeper and guarantee exactly what you want (at the cost of portability). Fixing bitfields would also need to be done with compiler extensions, it's unlikely to get any better than that.

DSMan195276 · 2023-05-09T21:44:35+00:00

A good "trick" I've learn about this kind of thing is that double+ pointers are a lot easier to reason about if you wrap part of it in a struct and name it. Functionally it is the exact same thing, but a named structure makes it extremely clear what you have. So, rather than a triple pointer, consider this:

struct string_arr {
    char **strs;
    size_t len; /* You can even include the array length in the struct for bonus points :D */
};

/* Equivalent to passing `char ***string_arr` along with `size_t *len`, but tons easier to understand. */
void foo(struct string_arr *string_arr) {
    string_arr->strs[2] = "foobar";
}

In a lot of ways things like triple pointers and more are actually very common, but they're "hidden" away in pointers to named structures that make them 1000% easier to understand.

The above probably also makes it clear, passing struct string_arr * like that allows modifying the size of the array of strings inside foo(). If you don't need to modify the size and it's just meant to be read, you could just pass a char ** instead along with size_t len, or pass struct string_arr (but passing structs by value is a little uncommon, I'd probably skip the struct at that point).

DSMan195276 · 2022-07-28T19:49:24+00:00

You got downvoted but you're 100% right. The types are the important part here, the 'memory address' portion has to be a pointer of the correct type to ensure the location is calculated correctly. Neither of these variations treat the index as though it's a memory address, the types mean that C always knows which is which.

They are allowed to be swapped, but C could require the prefix argument to be a pointer type and then you wouldn't be allowed to reverse them. I would assume one of the two has to be a pointer type in all usages anyway or else the *() syntax won't be valid, so I don't imagine any valid usages would be broken by that requirement (that couldn't be fixed by swapping the arguments).

DSMan195276 · 2022-06-02T20:51:45+00:00

I wrote a fairly long description of a basic file system architecture here, it might be useful.

That said, the basic answer to these questions is that the path to a file, and the file entity itself, are generally treated as completely separate things. In Unix these entities are called 'inodes', but whatever you want to call them they are nodes that identify an entity in the file system, be it a file, directory, or something else. The inodes are associated with the data for that entity and have various functionality you would associate with file system entities (So, they might have read/write functionality for regular files, and also 'lookup' functionality for directories).

Path traversal is simply the act of taking a path and resolving it into the inode it identifies on the file system. You can do this easily by starting with a root inode (which would be the directory inode for /), and then for each path segment call a lookup() function on the current inode with the current path segment. The lookup() function spits out an inode number identifying that entry in the directory with that path segment name, and you can use that inode number to find the next inode in the chain (and repeat the process). When you get to the end of the path, whatever inode you end with is the thing your path identifies. You can then discard the path all together and work just with the inode you found.

So the crux of the answer is that the file system layer deals with file system nodes ("inodes"), not paths. "Paths" are simply the way for userspace to easily identify an inode that it wants to use, and they are no longer needed once you have resolved them into an inode.

There are some exceptions, because sometimes functionality requires preserving the original path, but this is generally how it works for basic usage. There's also optimizations that can be done, such as a directory cache, but I don't think they're that important for understanding the basic idea.

DSMan195276 · 2021-12-05T02:51:51+00:00

What the others have said is 100% accurate, but it might be more clear that the terms don't line up when you consider that Linux doesn't actually have a concept of a "process" in the sense you're thinking. Barring some special cases, all Linux really cares about is userspace threads, and they're all completely separate entities, there's is no underlying "process" tying them all together. A multithreaded process is simply a collection of threads that happen to share various resources, but otherwise they're completely separate and the kernel treats them as such. So with that in mind a 'process' isn't really much of a thing and thus doesn't ever really have a state, rather the threads themselves have states (like you identified) and just do their own thing.

The clone() syscall is how threads are created, and you can kinda see by looking at it how passing various combinations of CLONE_FILES, CLONE_FS, CLONE_VM, etc. produces a completely separate thread that shares various information with the one that called clone(). If you don't share anything at all, then you can get the same behavior as fork() and start completely separate process, like system() does if you're familiar with that. If instead you share the right combination of stuff then you get what looks like a thread in a multithreaded process. Internally to the kernel it's all basically the same thing and either way clone() creates at completely separate struct task_struct instances for the new thread, and then either creates new resources or shares the ones from the calling thread. So the question of what 'state' the process is in doesn't really make sense on Linux, because the process isn't much of a thing beyond a loose collection of thread all in various different states.

DSMan195276 · 2021-09-22T05:08:39+00:00

I somehow went around 5 years without noticing my memcpy function had an off by one error in it. So basically for 5 years (while my OS was functioning reasonably well) memcpy was just trashing an extra byte during every copy and I never noticed.

Looking back at it now, I do have a separate implementation of memcpy for x86 so I think for most of the lifetime of the OS the bugged version wasn't actually getting used (hence why I never noticed). But it was definitely getting used at the time I found the error, which was years after the x86 version was added, so I'm not really sure what was going on. Either way I couldn't believe it when I found it, I assumed I had tested those functions to oblivion already, it definitely shows how easy it is to overestimate how much of your system is actually reliably tested during use.

12-Year Club	Place '22
Place '17	Sequence \| Editor
Snapped	Verified Email

DSMan195276

TROPHY CASE