Holberton School Announces Corporate Partners Network

Exciting news – Holberton is introducing a new Corporate Partner’s Network as a way for organizations to support the vision of bringing diverse and qualified talent to the tech industry. Joined by Google, Scality, Accenture, and CloudNOW, Holberton is creating a way to further its dedication to providing quality tech education to the most. These Corporate Partners are in the unique position of being able to nurture their dedication to diversifying the tech industry while simultaneously benefiting as a direct result.

Holberton School Students participating in a Scality Hackathon

 

Why should you be a part of this?

At Holberton, quality and diversity are congruent. One of the reasons Holberton attracts individuals from varied backgrounds is thanks to its automated application process. Throughout the process applicants are given problems to solve, while remaining anonymous. This allows prospective students to focus on the content rather than how they are perceived by an admissions panel. This underscores that talent and motivation are what’s important at Holberton.

The no-upfront-cost model also helps the school to offer opportunities to students of many diverse backgrounds. It’s not news that often times the barrier blocking individuals from post-secondary education comes down to the financial stress. Holberton’s chosen formula of learn first, pay later opens the possibility of further education to many that would otherwise not be able to afford it.

At Holberton School, quality is key. The combination of project-based and peer learning allows students to learn in a more creative way. “Holberton School offers a truly innovative approach to education: focus on building reliable applications and scalable systems, take on real-world challenges, collaborate with your peers. A school every software engineer would have dreamt of!” explains Kate Volkova, Sr. Software Engineer at Microsoft. They say the mark of truly mastering a concept is when you are able to explain it simply to a peer. Holberton’s curriculum is a crash course in exactly that methodology.

 

How can you get involved?

Recruit directly from our diverse and highly-qualified talent pool. Being a part of Holberton School’s Corporate Partners program offers organizations the exclusive opportunity to hire students directly from the source. Vint Cerf, Chief Internet Evangelist at Google and anointed “father of the internet”, boasts Holberton’s curriculum “In their internships, students end up getting exposed to a pretty broad range of stuff at Google and that helps reinforce why they learned what they learned and why it’s important…” Holberton School is producing talented software engineers who have landed positions with companies like NASA, Tesla, LinkedIn, Apple, and Dropbox. Our students are not only landing jobs, they’re receiving 95% positive feedback from their managers.

Donate to help students with their cost of living. San Francisco’s cost of living is 62.2% higher than the national average. Our Corporate Partners are working to alleviate some of that financial burden. “Scality is excited to be a part of Holberton’s Corporate Partners Program where we can give back and positively impact our shared goal of removing barriers for those who cannot afford traditional higher education.” says Giorgio Regni, Scality CTO and Holberton Corporate Partner.

 

Holberton School co-founders, Sylvain Kalache and Julien Barbier pose with Board of Trustees Member Ne-Yo who is focusing on diversity at Holberton.

Interested in joining our Corporate Partner’s Network? Register here!

Navigating Your Way Through Tech

It’s no accident that Ludovic Galibert is finding success in his career. Senior Software Engineer at Netflix, he came to chat with Holberton School students about the ins and outs of navigating the tech industry from an engineer’s point of view. Holberton Students Sue Kalia and Lee Gaines interviewed Ludovic; asking him a myriad of questions from interview advice to favorite Netflix shows. Ludo detailed many pro tips including advising students to obtain a public library card and espousing the importance of what he referred to as ‘soft skills.’

The emphasis on development of professional soft skills (i.e., – effective communication, teamwork, etc.) ran a constant thread throughout all of Ludo’s answers. When asked about what characteristics a good engineer should have, he pointed to traits such as ‘determination’,  ‘resilience’ and being a ‘team player’ as well as noting not to “underestimate things like social skills and communication. You’ll have to talk to and work with a lot of people.” You can see these elements becoming habits by looking at Holberton’s curriculum. For example, all students participate in a project where they are split into two teams and each team self organizes into a corporation; there’s a CEO, a marketing “department”, a product development team, etc. Both teams are given the same problem and it’s a race against when the clock strikes 5:00 to solve the problem in a more efficient way than your opponent. Now that is certainly the type of project that produces resilient team players, that know how to communicate!

Furthering his point, when asked about how to go about landing an engineering job his answer focused on gaining experience, as well as interview preparation – “any type of interview here in Silicon Valley, or generally in tech, it’s all about preparation.” Preparation for interviews goes beyond learning the code. Interview preparation includes skills ranging from technical understanding to understanding social cues.

When Sue asked Ludovic if he had made any mistakes throughout his career, we gained an even clearer insight into the importance he places on soft skills. He gave an anecdote of a time when he wished he had been more selfless as a mentor to a group of junior engineers;

I would go back and learn more about mentoring because it’s really important for the next generation to think about that – take time to help people. That’s one of the reasons I wanted to be a mentor for Holberton.”

During the student Q&A, Ludo touched on a couple of the industry’s current pain points including diversity and inclusion. He reminded the audience to remember not to get so wrapped up in your career that you forget to take a step back and help people around you. It is clear Ludovic has a handle on the larger picture. Engineering success seems to be a delicate balance of technical and non-technical skills.

 

Watch the full interview here.

Ludovic Galibert, Senior Software Engineer at Netflix & Holberton School Mentor, designs and implements highly scalable tools and services that indirectly impact millions of users.

Courageous Coding

Last night we were joined by Batch 2 rockstars, Naomi Sorrell and Kristen Loyd, who shared their secrets to maintaining success within the Holberton program with their pro tips and advice. In other words: it got real! The pair of students understand that there are many emotions and moods that come along with the fast paced nature of this program, and recognize that the struggle and the hard work make the learning much more gratifying.

They focused on ways to manage the course load with a few strategies that each student can mold into their own. The main strategies were broken down into six categories or themes:

  1. Assessing the situation
  2. Whiteboarding
  3. Time Management
  4. Communication
  5. Self Care
  6. Support Network

To highlight a few golden nuggets of wisdom, let’s focus on a few of these. Whiteboarding is something that Kristen and Naomi take seriously! The two regaled us with an anecdote of a four day project they were given of which they spent three of those days solely whiteboarding the code for understanding. This was the main point of the two aspiring engineers. They both agree that whiteboarding helps them fully understand the code they’re going to push out before they jump right to their computers. Check out Kristen walking us through a problem here.

Time management is something that so obvious that many forget to budget their time. Naomi suggests using timers to keep yourself on task. She explains the feeling of frustration from working a problem and getting the same error over and over. However, with a timer you can measure your progress. She suggests picking a length of time that feels comfortable for you and once you hit 20, 30, or even 40 minutes the timer will go off and signal to you that you should reach out and ask someone for help.

Building and embracing a strong support network seems to be the secret sauce. Both Naomi and Kristen emphasize the strong community aspect at Holberton as an underlying catalyst for their success. Actions as simple as understanding when your partner needs to take a walk around the block, grabbing a quick sweet treat, or even just asking a classmate for help all aid in creating the strong bonds we see between the students.


When following up with Naomi and Kristen they shared some final thoughts with me that seem to sum up the culture and environment Holberton prides itself on. In their own words:

“Grateful for such an engaged community that is always cooperatively exploring ways to grow as future engineers and empathetic humans.” – Naomi Sorrell

“Energized by the amount of conversation it sparked during and after the workshop; we are continuing to create a supportive community where we grow as individuals and take ownership of our education and goals.” – Kristen Loyd

Chat with Naomi about all things tech & community on Twitter and LinkedIn
Kristen loves to talk tech & whiteboarding on Twitter and LinkedIn

Batch One – Year One complete and it rocked our socks!

Our batch 01 students have graced the halls of Holberton and as their first year winds to a close, we have some exceptional success numbers!

80% of batch 01 students are already working in the tech industry as software engineers. WOOT!

 

 

Students have landed jobs and internships in companies like Tesla, Apple, NVIDIA, Scality, Dropbox, Docker, Shopkick and so many more exciting startups. Our program lasts a period of 2 years, but many of our students already have jobs within the first year! How cool is that?

If you haven’t checked out the video of our students story yet, take a few minutes and watch it here.

Hear what some of our students have to say about their current roles in the tech industry:

 

 

Swati Gupta, Software Engineer at NVIDIA says,

 

Holberton prepared me with tons of useful skills that are needed for a fast paced tech job, not just technical skills but soft skills too. I learned how to navigate, how to find the right tools and when to seek help. It made me a constant self learner, always adapting and accommodating to new information. The projects I did at Holberton were targeted at exposing all stacks of an application and based on latest technology, for instance the exposure to use docker containers. Because of the training I received at Holberton I feel more confident and prepared for my work life at NVIDIA

 

         

 

Anne Cognet, Software Engineer at TESLA says,

 

Holberton helped me get my internship at TESLA in so many ways. The school curriculum constantly pushed me to go deeper and do better. My classmates were very supportive, their approaches and questions helped me understand new concepts and gave me new ideas for solving problems. The school network helped me polish my resume as well. At my workplace, I am understanding & implementing the topics that I learned at Holberton. I believe the school gave me a strong foundation I can rely upon, and that makes me learn faster.

Before we look ahead to accomplishing anything further, we wanted to thank our community of mentors, students and team who helped make this year such a success.

Applications are now open for the January 2018 batch, you can learn more about it here.

Summer 2017 | Holberton Coding Camp

 This Summer, we introduced our very first Holberton Summer Coding Camp!

Eight shining stars from multiple different high schools in the San Francisco Bay Area went from no programming experience to web development rock stars in 3 short weeks.

 

 

Our campers were high school students aged 15-18 years old with no previous web development experience. They joined our camp wanting to discover new skills and explore the tech industry.

Over the course of 3 weeks, students learned the fundamentals of web development (HTML, CSS, JS), and then took their new found skills to build their own multi-paged websites from A to Z. They even added some extra pixel dust to their websites with super cool CSS animations, embedded links, menu bar and web content. An impressive feat for any software engineer, let alone beginners! 

Technical skills were the focus over the three weeks, but their soft skills were sharpened as well, especially public speaking! Our campers learned how to present in front of people and explore the art of networking with professionals.


 

Every week, students visited some of the hottest tech companies in the SF Bay Area namely Salesforce, Trinity Ventures and exciting startups like Scality and Twitch. They discovered what working in a tech company looks like and realized the value and importance of having a professional network. More than that, they understood what it takes to be a software engineer!


 

At Holberton we have no formal teachers, students learn by helping each other in the projects and our Coding Camp was no different. Our campers went through the sweet journey of practicing peer learning while working hard to code their websites, but were also well supported with current Holberton students and mentors, who are professionals working in the Tech industry.

 

         

 

Our amazing mentors held workshops for our campers to build new skills. Ayesha Mazumdar, UX Engineer at Salesforce, led our campers through an animation workshop. Jennie Chu, a Holberton student, now Software Engineer at SeeSaw, taught our campers how to solder to make keyboards from scratch. The cherry on the top was when NE-YO personally called our campers to talk about their goals in life and how they could achieve them after breaking the programming-ice with Holberton!

 

 

Every day was about having fun while learning with mentors, peers, staff and of course eating a whole lot of french brie & baguette (After all we are a french led startup)! 

The students had the motivation and drive within, all they needed was an eye opener like our camp to empower them to discover their capabilities in software engineering.

Hear what our campers had to say about their experience at Holberton:

“ Anyone considering being a software engineer would benefit extremely from this camp. What really sets the camp apart is that you get a taste of how the real world works in tech. The project of building your own website can be compared to doing a project in a company where you ask your peers/co-workers for help.”

“This camp offers great opportunities, and the experience is amazing. They also teach very important skills that don’t only apply to the tech industry but life in general (ex. learning how to learn).”

“I had no idea how to code coming into the camp, and after 3 weeks I understand code and technology way better. It was a great experience overall. Also, the opportunity to visit big companies in the city is hard to find anywhere else.”

Our first summer camp was a success, and we will keep taking initiatives to give the world the talent it deserves. If you’re interested in enrolling for our next coding camp, please fill out this form and we will keep you posted on future camps!

New York Times features Holberton, now this is BIG!

Today we are super happy and we feel PUMPED! **insertmoonwalk**

We have smiles all around while we share this exciting news with you…  This morning, Holberton got covered in the  The New York Times, the source the world goes to for the facts!

 

“The main thing we’re learning is how to learn,” said Dora Korpar, Holberton student, who recently accepted a job offer from Scality, a Silicon Valley company.

In this article, Holberton, a Two-Year Tech School, Emphasizes Diversity’, Katie Benner delves into the world of Holberton, while capturing the very essence of what makes Holberton different from other schools and bootcamps.

The article also touches on how Holberton is removing barriers and motivating people from diverse backgrounds come and build a career in tech. With proven records of getting students jobs at Apple, NASA and LinkedIn, even though they have not yet graduated.

 

 

“We want to remove any barrier to a high-quality education,” said Sylvain, Co-founder, Holberton School. “No matter your age, gender, ethnicity or past professional life, you can come.”

“I was attracted to Holberton because my school is also about social justice and teaching populations that are frozen out of the information age, meaning people of color, women and people who are not wealthy,” said Vito Ferrante, A Director of educational technology at Sacred Heart Cathedral Preparatory in San Francisco.

Thanks Katie Benner for interviewing our team and curating the fantastic story.

We feel honored and want to share our happiness with all of you – Thank you for being a part of our journey. We all are thrilled to go further and make our school even better.

Looking forward to more exciting times!

Click here to read the full article.

Show us some love, Share the article 🙂

Spot. Click. Share. Contest

Hello Friends, while you read this blog on your phone in BART, one of our students may be journeying with you! No, like SERIOUSLY! Our dear students are traveling with you in the subway trains every day… Haven’t you noticed them yet?

 

Holberton students are riding along with you in San Francisco Bay Area public transport BART on posters… Our students started to have some fun by taking cool selfies with the posters, so we thought of sharing the fun with you too!

 

We decided to organize a contest for all of you! Isn’t that a mega-exciting Llama farm fun news?

Ready…. Set…. ARDUINO….

If you have a passion for Arduino or you tinker, hack, make or create cool stuff, then this contest is for you! Tinkerers, rejoice! We are excited to announce the “Spot. Click. Share” contest that sponsors an Arduino Starter Kit for the winner.

Simple steps to enter the contest:

  1. SPOT: Find Holberton school’s poster in Bart while traveling.
  2. CLICK: Click a selfie with the poster.
  3. SHARE: Share it on social media (Facebook, Instagram or Twitter) with #YouCanToo and tag us @holbertonschool.

 

Rules for the contest:

  • Open to all BART travelers in the SF Bay Area.
  • The most creative picture with a caption wins.
  • The post must have the hashtag #YouCanToo.
  • The contest ends on June 22nd, 2017.
  • The results will be announced on June 26th, 2017.

To improve your odds of winning, you can make sure your picture receives more reposts/retweets/shares and likes. So put your creative caps on, share your picture with us in the most creative way you can.

The thought of winning this cool Arduino Starter Kit should alone be enough to make you break out your soldering iron!

Good luck and happy spotting, clicking & sharing!

Holberton launches Summer Coding Camp!

Holberton is launching it’s inaugural Summer Coding Camp! This is a 3-week Summer Coding Camp for 15 to 18 year olds where students will not attend class but will be learning through  building their first website, following our progressive education methodology focusing on learning by doing.

Over the course of the camp, tech companies will tour their offices to students, in addition to collaborating with current Holberton students and mentors, so that our campers will gain exposure and keen insights on what it takes to become a professional in the tech industry.

GRAMMY award-winning artist NE-YO is part of the mentor team, he recently joined the school’s Board of Trustees to help attract underrepresented groups to software engineering. NE-YO will be reviewing our campers’ progress personally.

NE-YO doing a Q&A with Holberton students

Following Holberton’s mission to make high quality education accessible to the most, the 3-week camp is totally free and can even accommodate for those who cannot afford transportation and food.

The coding camp will cover the basics of HTML, CSS and Javascript. Students will learn to build their first website and personalize it to their taste. Mentors from Silicon Valley Tech companies will come to the school to coach them and give feedback on their performance during the demo day.
The camps starts on June 26th and applications are now open! If you want to support this initiative, please help us spread the word!

Hack the Virtual Memory: malloc, the heap & the program break

Hack the VM!

This is the fourth chapter in a series around virtual memory. The goal is to learn some CS basics, but in a different and more practical way.

If you missed the previous chapters, you should probably start there:

The heap

In this chapter we will look at the heap and malloc in order to answer some of the questions we ended with at the end of the previous chapter:

  • Why doesn’t our allocated memory start at the very beginning of the heap (0x2050010 vs 02050000)? What are those first 16 bytes used for?
  • Is the heap actually growing upwards?

Prerequisites

In order to fully understand this article, you will need to know:

Environment

All scripts and programs have been tested on the following system:

  • Ubuntu
    • Linux ubuntu 4.4.0-31-generic #50~14.04.1-Ubuntu SMP Wed Jul 13 01:07:32 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

Tools used:

  • gcc
    • gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
  • glibc 2.19 (see version.c if you need to check your glibc version)
  • strace
    • strace — version 4.8

Everything we will write will be true for this system/environment, but may be different on another system

We will also go through the Linux source code. If you are on Ubuntu, you can download the sources of your current kernel by running this command:

apt-get source linux-image-$(uname -r)

malloc

malloc is the common function used to dynamically allocate memory. This memory is allocated on the “heap”.
Note: malloc is not a system call.

From man malloc:

[...] allocate dynamic memory[...]
void *malloc(size_t size);
[...]
The malloc() function allocates size bytes and returns a pointer to the allocated memory.

No malloc, no [heap]

Let’s look at memory regions of a process that does not call malloc (0-main.c).

#include <stdlib.h>
#include <stdio.h>

/**
 * main - do nothing
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    getchar();
    return (EXIT_SUCCESS);
}

julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 0-main.c -o 0
julien@holberton:~/holberton/w/hackthevm3$ ./0 

Quick reminder (1/3): the memory regions of a process are listed in the /proc/[pid]/maps file. As a result, we first need to know the PID of the process. That is done using the ps command; the second column of ps aux output will give us the PID of the process. Please read chapter 0 to learn more.

julien@holberton:/tmp$ ps aux | grep \ \./0$
julien     3638  0.0  0.0   4200   648 pts/9    S+   12:01   0:00 ./0

Quick reminder (2/3): from the above output, we can see that the PID of the process we want to look at is 3638. As a result, the maps file will be found in the directory /proc/3638.

julien@holberton:/tmp$ cd /proc/3638

Quick reminder (3/3): The maps file contains the memory regions of the process. The format of each line in this file is:
address perms offset dev inode pathname

julien@holberton:/proc/3638$ cat maps
00400000-00401000 r-xp 00000000 08:01 174583                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/0
00600000-00601000 r--p 00000000 08:01 174583                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/0
00601000-00602000 rw-p 00001000 08:01 174583                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/0
7f38f87d7000-7f38f8991000 r-xp 00000000 08:01 136253                     /lib/x86_64-linux-gnu/libc-2.19.so
7f38f8991000-7f38f8b91000 ---p 001ba000 08:01 136253                     /lib/x86_64-linux-gnu/libc-2.19.so
7f38f8b91000-7f38f8b95000 r--p 001ba000 08:01 136253                     /lib/x86_64-linux-gnu/libc-2.19.so
7f38f8b95000-7f38f8b97000 rw-p 001be000 08:01 136253                     /lib/x86_64-linux-gnu/libc-2.19.so
7f38f8b97000-7f38f8b9c000 rw-p 00000000 00:00 0 
7f38f8b9c000-7f38f8bbf000 r-xp 00000000 08:01 136229                     /lib/x86_64-linux-gnu/ld-2.19.so
7f38f8da3000-7f38f8da6000 rw-p 00000000 00:00 0 
7f38f8dbb000-7f38f8dbe000 rw-p 00000000 00:00 0 
7f38f8dbe000-7f38f8dbf000 r--p 00022000 08:01 136229                     /lib/x86_64-linux-gnu/ld-2.19.so
7f38f8dbf000-7f38f8dc0000 rw-p 00023000 08:01 136229                     /lib/x86_64-linux-gnu/ld-2.19.so
7f38f8dc0000-7f38f8dc1000 rw-p 00000000 00:00 0 
7ffdd85c5000-7ffdd85e6000 rw-p 00000000 00:00 0                          [stack]
7ffdd85f2000-7ffdd85f4000 r--p 00000000 00:00 0                          [vvar]
7ffdd85f4000-7ffdd85f6000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
julien@holberton:/proc/3638$ 

Note: hackthevm3 is a symbolic link to hack_the_virtual_memory/03. The Heap/

-> As we can see from the above maps file, there’s no [heap] region allocated.

malloc(x)

Let’s do the same but with a program that calls malloc (1-main.c):

#include <stdio.h>
#include <stdlib.h>

/**
 * main - 1 call to malloc
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    malloc(1);
    getchar();
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 1-main.c -o 1
julien@holberton:~/holberton/w/hackthevm3$ ./1 

julien@holberton:/proc/3638$ ps aux | grep \ \./1$
julien     3718  0.0  0.0   4332   660 pts/9    S+   12:09   0:00 ./1
julien@holberton:/proc/3638$ cd /proc/3718
julien@holberton:/proc/3718$ cat maps 
00400000-00401000 r-xp 00000000 08:01 176964                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/1
00600000-00601000 r--p 00000000 08:01 176964                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/1
00601000-00602000 rw-p 00001000 08:01 176964                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/1
01195000-011b6000 rw-p 00000000 00:00 0                                  [heap]
...
julien@holberton:/proc/3718$ 

-> the [heap] is here.

Let’s check the return value of malloc to make sure the returned address is in the heap region (2-main.c):

#include <stdio.h>
#include <stdlib.h>

/**
 * main - prints the malloc returned address
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    void *p;

    p = malloc(1);
    printf("%p\n", p);
    getchar();
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 2-main.c -o 2
julien@holberton:~/holberton/w/hackthevm3$ ./2 
0x24d6010

julien@holberton:/proc/3718$ ps aux | grep \ \./2$
julien     3834  0.0  0.0   4336   676 pts/9    S+   12:48   0:00 ./2
julien@holberton:/proc/3718$ cd /proc/3834
julien@holberton:/proc/3834$ cat maps
00400000-00401000 r-xp 00000000 08:01 176966                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/2
00600000-00601000 r--p 00000000 08:01 176966                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/2
00601000-00602000 rw-p 00001000 08:01 176966                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/2
024d6000-024f7000 rw-p 00000000 00:00 0                                  [heap]
...
julien@holberton:/proc/3834$ 

-> 024d6000 <0x24d6010 < 024f7000

The returned address is inside the heap region. And as we have seen in the previous chapter, the returned address does not start exactly at the beginning of the region; we’ll see why later.

strace, brk and sbrk

malloc is a “regular” function (as opposed to a system call), so it must call some kind of syscall in order to manipulate the heap. Let’s use strace to find out.

strace is a program used to trace system calls and signals. Any program will always use a few syscalls before your main function is executed. In order to know which syscalls are used by malloc, we will add a write syscall before and after the call to malloc(3-main.c).

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/**
 * main - let's find out which syscall malloc is using
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    void *p;

    write(1, "BEFORE MALLOC\n", 14);
    p = malloc(1);
    write(1, "AFTER MALLOC\n", 13);
    printf("%p\n", p);
    getchar();
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 3-main.c -o 3
julien@holberton:~/holberton/w/hackthevm3$ strace ./3 
execve("./3", ["./3"], [/* 61 vars */]) = 0
...
write(1, "BEFORE MALLOC\n", 14BEFORE MALLOC
)         = 14
brk(0)                                  = 0xe70000
brk(0xe91000)                           = 0xe91000
write(1, "AFTER MALLOC\n", 13AFTER MALLOC
)          = 13
...
read(0, 

From the above listing we can focus on this:

brk(0)                                  = 0xe70000
brk(0xe91000)                           = 0xe91000

-> malloc is using the brk system call in order to manipulate the heap. From brk man page (man brk), we can see what this system call is doing:

...
       int brk(void *addr);
       void *sbrk(intptr_t increment);
...
DESCRIPTION
       brk() and sbrk() change the location of the program  break,  which  defines
       the end of the process's data segment (i.e., the program break is the first
       location after the end of the uninitialized data segment).  Increasing  the
       program  break has the effect of allocating memory to the process; decreas‐
       ing the break deallocates memory.

       brk() sets the end of the data segment to the value specified by addr, when
       that  value  is  reasonable,  the system has enough memory, and the process
       does not exceed its maximum data size (see setrlimit(2)).

       sbrk() increments the program's data space  by  increment  bytes.   Calling
       sbrk()  with  an increment of 0 can be used to find the current location of
       the program break.

The program break is the address of the first location beyond the current end of the data region of the program in the virual memory.

program break before the call to malloc / brk

By increasing the value of the program break, via brk or sbrk, the function malloc creates a new space that can then be used by the process to dynamically allocate memory (using malloc).

program break after the malloc / brk call

So the heap is actually an extension of the data segment of the program.

The first call to brk (brk(0)) returns the current address of the program break to malloc. And the second call is the one that actually creates new memory (since 0xe91000 > 0xe70000) by increasing the value of the program break. In the above example, the heap is now starting at 0xe70000 and ends at 0xe91000. Let’s double check with the /proc/[PID]/maps file:

julien@holberton:/proc/3855$ ps aux | grep \ \./3$
julien     4011  0.0  0.0   4748   708 pts/9    S+   13:04   0:00 strace ./3
julien     4014  0.0  0.0   4336   644 pts/9    S+   13:04   0:00 ./3
julien@holberton:/proc/3855$ cd /proc/4014
julien@holberton:/proc/4014$ cat maps 
00400000-00401000 r-xp 00000000 08:01 176967                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/3
00600000-00601000 r--p 00000000 08:01 176967                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/3
00601000-00602000 rw-p 00001000 08:01 176967                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/3
00e70000-00e91000 rw-p 00000000 00:00 0                                  [heap]
...
julien@holberton:/proc/4014$ 

-> 00e70000-00e91000 rw-p 00000000 00:00 0 [heap] matches the pointers returned back to malloc by brk.

That’s great, but wait, why didmalloc increment the heap by 00e9100000e70000 = 0x21000 or 135168 bytes, when we only asked for only 1 byte?

Many mallocs

What will happen if we call malloc several times? (4-main.c)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/**
 * main - many calls to malloc
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    void *p;

    write(1, "BEFORE MALLOC #0\n", 17);
    p = malloc(1024);
    write(1, "AFTER MALLOC #0\n", 16);
    printf("%p\n", p);

    write(1, "BEFORE MALLOC #1\n", 17);
    p = malloc(1024);
    write(1, "AFTER MALLOC #1\n", 16);
    printf("%p\n", p);

    write(1, "BEFORE MALLOC #2\n", 17);
    p = malloc(1024);
    write(1, "AFTER MALLOC #2\n", 16);
    printf("%p\n", p);

    write(1, "BEFORE MALLOC #3\n", 17);
    p = malloc(1024);
    write(1, "AFTER MALLOC #3\n", 16);
    printf("%p\n", p);

    getchar();
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 4-main.c -o 4
julien@holberton:~/holberton/w/hackthevm3$ strace ./4 
execve("./4", ["./4"], [/* 61 vars */]) = 0
...
write(1, "BEFORE MALLOC #0\n", 17BEFORE MALLOC #0
)      = 17
brk(0)                                  = 0x1314000
brk(0x1335000)                          = 0x1335000
write(1, "AFTER MALLOC #0\n", 16AFTER MALLOC #0
)       = 16
...
write(1, "0x1314010\n", 100x1314010
)             = 10
write(1, "BEFORE MALLOC #1\n", 17BEFORE MALLOC #1
)      = 17
write(1, "AFTER MALLOC #1\n", 16AFTER MALLOC #1
)       = 16
write(1, "0x1314420\n", 100x1314420
)             = 10
write(1, "BEFORE MALLOC #2\n", 17BEFORE MALLOC #2
)      = 17
write(1, "AFTER MALLOC #2\n", 16AFTER MALLOC #2
)       = 16
write(1, "0x1314830\n", 100x1314830
)             = 10
write(1, "BEFORE MALLOC #3\n", 17BEFORE MALLOC #3
)      = 17
write(1, "AFTER MALLOC #3\n", 16AFTER MALLOC #3
)       = 16
write(1, "0x1314c40\n", 100x1314c40
)             = 10
...
read(0, 

-> malloc is NOT calling brk each time we call it.

The first time, malloc creates a new space (the heap) for the program (by increasing the program break location). The following times, malloc uses the same space to give our program “new” chunks of memory. Those “new” chunks of memory are part of the memory previously allocated using brk. This way, malloc doesn’t have to use syscalls (brk) every time we call it, and thus it makes malloc – and our programs using malloc – faster. It also allows malloc and free to optimize the usage of the memory.

Let’s double check that we have only one heap, allocated by the first call to brk:

julien@holberton:/proc/4014$ ps aux | grep \ \./4$
julien     4169  0.0  0.0   4748   688 pts/9    S+   13:33   0:00 strace ./4
julien     4172  0.0  0.0   4336   656 pts/9    S+   13:33   0:00 ./4
julien@holberton:/proc/4014$ cd /proc/4172
julien@holberton:/proc/4172$ cat maps
00400000-00401000 r-xp 00000000 08:01 176973                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/4
00600000-00601000 r--p 00000000 08:01 176973                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/4
00601000-00602000 rw-p 00001000 08:01 176973                             /home/julien/holberton/w/hack_the_virtual_memory/03. The Heap/4
01314000-01335000 rw-p 00000000 00:00 0                                  [heap]
7f4a3f2c4000-7f4a3f47e000 r-xp 00000000 08:01 136253                     /lib/x86_64-linux-gnu/libc-2.19.so
7f4a3f47e000-7f4a3f67e000 ---p 001ba000 08:01 136253                     /lib/x86_64-linux-gnu/libc-2.19.so
7f4a3f67e000-7f4a3f682000 r--p 001ba000 08:01 136253                     /lib/x86_64-linux-gnu/libc-2.19.so
7f4a3f682000-7f4a3f684000 rw-p 001be000 08:01 136253                     /lib/x86_64-linux-gnu/libc-2.19.so
7f4a3f684000-7f4a3f689000 rw-p 00000000 00:00 0 
7f4a3f689000-7f4a3f6ac000 r-xp 00000000 08:01 136229                     /lib/x86_64-linux-gnu/ld-2.19.so
7f4a3f890000-7f4a3f893000 rw-p 00000000 00:00 0 
7f4a3f8a7000-7f4a3f8ab000 rw-p 00000000 00:00 0 
7f4a3f8ab000-7f4a3f8ac000 r--p 00022000 08:01 136229                     /lib/x86_64-linux-gnu/ld-2.19.so
7f4a3f8ac000-7f4a3f8ad000 rw-p 00023000 08:01 136229                     /lib/x86_64-linux-gnu/ld-2.19.so
7f4a3f8ad000-7f4a3f8ae000 rw-p 00000000 00:00 0 
7ffd1ba73000-7ffd1ba94000 rw-p 00000000 00:00 0                          [stack]
7ffd1bbed000-7ffd1bbef000 r--p 00000000 00:00 0                          [vvar]
7ffd1bbef000-7ffd1bbf1000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
julien@holberton:/proc/4172$ 

-> We have only one [heap] and the addresses match those returned by sbrk: 0x1314000 & 0x1335000

Naive malloc

Based on the above, and assuming we won’t ever need to free anything, we can now write our own (naive) version of malloc, that would move the program break each time it is called.

#include <stdlib.h>
#include <unistd.h>

/**                                                                                            
 * malloc - naive version of malloc: dynamically allocates memory on the heap using sbrk                         
 * @size: number of bytes to allocate                                                          
 *                                                                                             
 * Return: the memory address newly allocated, or NULL on error                                
 *                                                                                             
 * Note: don't do this at home :)                                                              
 */
void *malloc(size_t size)
{
    void *previous_break;

    previous_break = sbrk(size);
    /* check for error */
    if (previous_break == (void *) -1)
    {
        /* on error malloc returns NULL */
        return (NULL);
    }
    return (previous_break);
}

The 0x10 lost bytes

If we look at the output of the previous program (4-main.c), we can see that the first memory address returned by malloc doesn’t start at the beginning of the heap, but 0x10 bytes after: 0x1314010 vs 0x1314000. Also, when we call malloc(1024) a second time, the address should be 0x1314010 (the returned value of the first call to malloc) + 1024 (or 0x400 in hexadecimal, since the first call to malloc was asking for 1024 bytes) = 0x1318010. But the return value of the second call to malloc is 0x1314420. We have lost 0x10 bytes again! Same goes for the subsequent calls.

Let’s look at what we can find inside those “lost” 0x10-byte memory spaces (5-main.c) and whether the memory loss stays constant:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/**                                                                                            
 * pmem - print mem                                                                            
 * @p: memory address to start printing from                                                   
 * @bytes: number of bytes to print                                                            
 *                                                                                             
 * Return: nothing                                                                             
 */
void pmem(void *p, unsigned int bytes)
{
    unsigned char *ptr;
    unsigned int i;

    ptr = (unsigned char *)p;
    for (i = 0; i < bytes; i++)
    {
        if (i != 0)
        {
            printf(" ");
        }
        printf("%02x", *(ptr + i));
    }
    printf("\n");
}

/**
 * main - the 0x10 lost bytes
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    void *p;
    int i;

    for (i = 0; i < 10; i++)
    {
        p = malloc(1024 * (i + 1));
        printf("%p\n", p);
        printf("bytes at %p:\n", (void *)((char *)p - 0x10));
        pmem((char *)p - 0x10, 0x10);
    }
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 5-main.c -o 5
julien@holberton:~/holberton/w/hackthevm3$ ./5
0x1fa8010
bytes at 0x1fa8000:
00 00 00 00 00 00 00 00 11 04 00 00 00 00 00 00
0x1fa8420
bytes at 0x1fa8410:
00 00 00 00 00 00 00 00 11 08 00 00 00 00 00 00
0x1fa8c30
bytes at 0x1fa8c20:
00 00 00 00 00 00 00 00 11 0c 00 00 00 00 00 00
0x1fa9840
bytes at 0x1fa9830:
00 00 00 00 00 00 00 00 11 10 00 00 00 00 00 00
0x1faa850
bytes at 0x1faa840:
00 00 00 00 00 00 00 00 11 14 00 00 00 00 00 00
0x1fabc60
bytes at 0x1fabc50:
00 00 00 00 00 00 00 00 11 18 00 00 00 00 00 00
0x1fad470
bytes at 0x1fad460:
00 00 00 00 00 00 00 00 11 1c 00 00 00 00 00 00
0x1faf080
bytes at 0x1faf070:
00 00 00 00 00 00 00 00 11 20 00 00 00 00 00 00
0x1fb1090
bytes at 0x1fb1080:
00 00 00 00 00 00 00 00 11 24 00 00 00 00 00 00
0x1fb34a0
bytes at 0x1fb3490:
00 00 00 00 00 00 00 00 11 28 00 00 00 00 00 00
julien@holberton:~/holberton/w/hackthevm3$ 

There is one clear pattern: the size of the malloc’ed memory chunk is always found in the preceding 0x10 bytes. For instance, the first malloc call is malloc’ing 1024 (0x0400) bytes and we can find 11 04 00 00 00 00 00 00 in the preceding 0x10 bytes. Those last bytes represent the number 0x 00 00 00 00 00 00 04 11 = 0x400 (1024) + 0x10 (the block size preceding those 1024 bytes + 1 (we’ll talk about this “+1” later in this chapter). If we look at each 0x10 bytes preceding the addresses returned by malloc, they all contain the size of the chunk of memory asked to malloc + 0x10 + 1.

At this point, given what we said and saw earlier, we can probably guess that those 0x10 bytes are a sort of data structure used by malloc (and free) to deal with the heap. And indeed, even though we don’t understand everything yet, we can already use this data structure to go from one malloc’ed chunk of memory to the other (6-main.c) as long as we have the address of the beginning of the heap (and as long as we have never called free):

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/**                                                                                            
 * pmem - print mem                                                                            
 * @p: memory address to start printing from                                                   
 * @bytes: number of bytes to print                                                            
 *                                                                                             
 * Return: nothing                                                                             
 */
void pmem(void *p, unsigned int bytes)
{
    unsigned char *ptr;
    unsigned int i;

    ptr = (unsigned char *)p;
    for (i = 0; i < bytes; i++)
    {
        if (i != 0)
        {
            printf(" ");
        }
        printf("%02x", *(ptr + i));
    }
    printf("\n");
}

/**
 * main - using the 0x10 bytes to jump to next malloc'ed chunks
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    void *p;
    int i;
    void *heap_start;
    size_t size_of_the_block;

    heap_start = sbrk(0);
    write(1, "START\n", 6);
    for (i = 0; i < 10; i++)
    {
        p = malloc(1024 * (i + 1)); 
        *((int *)p) = i;
        printf("%p: [%i]\n", p, i);
    }
    p = heap_start;
    for (i = 0; i < 10; i++)
    {
        pmem(p, 0x10);
        size_of_the_block = *((size_t *)((char *)p + 8)) - 1;
        printf("%p: [%i] - size = %lu\n",
              (void *)((char *)p + 0x10),
              *((int *)((char *)p + 0x10)),
              size_of_the_block);
        p = (void *)((char *)p + size_of_the_block);
    }
    write(1, "END\n", 4);
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 6-main.c -o 6
julien@holberton:~/holberton/w/hackthevm3$ ./6 
START
0x9e6010: [0]
0x9e6420: [1]
0x9e6c30: [2]
0x9e7840: [3]
0x9e8850: [4]
0x9e9c60: [5]
0x9eb470: [6]
0x9ed080: [7]
0x9ef090: [8]
0x9f14a0: [9]
00 00 00 00 00 00 00 00 11 04 00 00 00 00 00 00
0x9e6010: [0] - size = 1040
00 00 00 00 00 00 00 00 11 08 00 00 00 00 00 00
0x9e6420: [1] - size = 2064
00 00 00 00 00 00 00 00 11 0c 00 00 00 00 00 00
0x9e6c30: [2] - size = 3088
00 00 00 00 00 00 00 00 11 10 00 00 00 00 00 00
0x9e7840: [3] - size = 4112
00 00 00 00 00 00 00 00 11 14 00 00 00 00 00 00
0x9e8850: [4] - size = 5136
00 00 00 00 00 00 00 00 11 18 00 00 00 00 00 00
0x9e9c60: [5] - size = 6160
00 00 00 00 00 00 00 00 11 1c 00 00 00 00 00 00
0x9eb470: [6] - size = 7184
00 00 00 00 00 00 00 00 11 20 00 00 00 00 00 00
0x9ed080: [7] - size = 8208
00 00 00 00 00 00 00 00 11 24 00 00 00 00 00 00
0x9ef090: [8] - size = 9232
00 00 00 00 00 00 00 00 11 28 00 00 00 00 00 00
0x9f14a0: [9] - size = 10256
END
julien@holberton:~/holberton/w/hackthevm3$ 

One of our open questions from the previous chapter is now answered: malloc is using 0x10 additional bytes for each malloc’ed memory block to store the size of the block.

0x10 bytes preceeding malloc

This data will actually be used by free to save it to a list of available blocks for future calls to malloc.

But our study also raises a new question: what are the first 8 bytes of the 16 (0x10 in hexadecimal) bytes used for? It seems to always be zero. Is it just padding?

RTFSC

At this stage, we probably want to check the source code of malloc to confirm what we just found (malloc.c from the glibc).

1055 /*
1056       malloc_chunk details:
1057    
1058        (The following includes lightly edited explanations by Colin Plumb.)
1059    
1060        Chunks of memory are maintained using a `boundary tag' method as
1061        described in e.g., Knuth or Standish.  (See the paper by Paul
1062        Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
1063        survey of such techniques.)  Sizes of free chunks are stored both
1064        in the front of each chunk and at the end.  This makes
1065        consolidating fragmented chunks into bigger chunks very fast.  The
1066        size fields also hold bits representing whether chunks are free or
1067        in use.
1068    
1069        An allocated chunk looks like this:
1070    
1071    
1072        chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1073                |             Size of previous chunk, if unallocated (P clear)  |
1074                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1075                |             Size of chunk, in bytes                     |A|M|P|
1076          mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1077                |             User data starts here...                          .
1078                .                                                               .
1079                .             (malloc_usable_size() bytes)                      .
1080                .                                                               |
1081    nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1082                |             (size of chunk, but used for application data)    |
1083                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1084                |             Size of next chunk, in bytes                |A|0|1|
1085                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1086    
1087        Where "chunk" is the front of the chunk for the purpose of most of
1088        the malloc code, but "mem" is the pointer that is returned to the
1089        user.  "Nextchunk" is the beginning of the next contiguous chunk.

-> We were correct \o/. Right before the address returned by malloc to the user, we have two variables:

  • Size of previous chunk, if unallocated: we never free’d any chunks so that is why it was always 0
  • Size of chunk, in bytes

Let’s free some chunks to confirm that the first 8 bytes are used the way the source code describes it (7-main.c):

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/**                                                                                            
 * pmem - print mem                                                                            
 * @p: memory address to start printing from                                                   
 * @bytes: number of bytes to print                                                            
 *                                                                                             
 * Return: nothing                                                                             
 */
void pmem(void *p, unsigned int bytes)
{
    unsigned char *ptr;
    unsigned int i;

    ptr = (unsigned char *)p;
    for (i = 0; i < bytes; i++)
    {
        if (i != 0)
        {
            printf(" ");
        }
        printf("%02x", *(ptr + i));
    }
    printf("\n");
}

/**
 * main - confirm the source code
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    void *p;
    int i;
    size_t size_of_the_chunk;
    size_t size_of_the_previous_chunk;
    void *chunks[10];

    for (i = 0; i < 10; i++)
    {
        p = malloc(1024 * (i + 1));
        chunks[i] = (void *)((char *)p - 0x10);
        printf("%p\n", p);
    }
    free((char *)(chunks[3]) + 0x10);
    free((char *)(chunks[7]) + 0x10);
    for (i = 0; i < 10; i++)
    {
        p = chunks[i];
        printf("chunks[%d]: ", i);
        pmem(p, 0x10);
        size_of_the_chunk = *((size_t *)((char *)p + 8)) - 1;
        size_of_the_previous_chunk = *((size_t *)((char *)p));
        printf("chunks[%d]: %p, size = %li, prev = %li\n",
              i, p, size_of_the_chunk, size_of_the_previous_chunk);
    }
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 7-main.c -o 7
julien@holberton:~/holberton/w/hackthevm3$ ./7
0x1536010
0x1536420
0x1536c30
0x1537840
0x1538850
0x1539c60
0x153b470
0x153d080
0x153f090
0x15414a0
chunks[0]: 00 00 00 00 00 00 00 00 11 04 00 00 00 00 00 00
chunks[0]: 0x1536000, size = 1040, prev = 0
chunks[1]: 00 00 00 00 00 00 00 00 11 08 00 00 00 00 00 00
chunks[1]: 0x1536410, size = 2064, prev = 0
chunks[2]: 00 00 00 00 00 00 00 00 11 0c 00 00 00 00 00 00
chunks[2]: 0x1536c20, size = 3088, prev = 0
chunks[3]: 00 00 00 00 00 00 00 00 11 10 00 00 00 00 00 00
chunks[3]: 0x1537830, size = 4112, prev = 0
chunks[4]: 10 10 00 00 00 00 00 00 10 14 00 00 00 00 00 00
chunks[4]: 0x1538840, size = 5135, prev = 4112
chunks[5]: 00 00 00 00 00 00 00 00 11 18 00 00 00 00 00 00
chunks[5]: 0x1539c50, size = 6160, prev = 0
chunks[6]: 00 00 00 00 00 00 00 00 11 1c 00 00 00 00 00 00
chunks[6]: 0x153b460, size = 7184, prev = 0
chunks[7]: 00 00 00 00 00 00 00 00 11 20 00 00 00 00 00 00
chunks[7]: 0x153d070, size = 8208, prev = 0
chunks[8]: 10 20 00 00 00 00 00 00 10 24 00 00 00 00 00 00
chunks[8]: 0x153f080, size = 9231, prev = 8208
chunks[9]: 00 00 00 00 00 00 00 00 11 28 00 00 00 00 00 00
chunks[9]: 0x1541490, size = 10256, prev = 0
julien@holberton:~/holberton/w/hackthevm3$ 

As we can see from the above listing, when the previous chunk has been free’d, the malloc chunk’s first 8 bytes contain the size of the previous unallocated chunk. So the correct representation of a malloc chunk is the following:

malloc chunk

Also, it seems that the first bit of the next 8 bytes (containing the size of the current chunk) serves as a flag to check if the previous chunk is used (1) or not (0). So the correct updated version of our program should be written this way (8-main.c):

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/**                                                                                            
 * pmem - print mem                                                                            
 * @p: memory address to start printing from                                                   
 * @bytes: number of bytes to print                                                            
 *                                                                                             
 * Return: nothing                                                                             
 */
void pmem(void *p, unsigned int bytes)
{
    unsigned char *ptr;
    unsigned int i;

    ptr = (unsigned char *)p;
    for (i = 0; i < bytes; i++)
    {
        if (i != 0)
        {
            printf(" ");
        }
        printf("%02x", *(ptr + i));
    }
    printf("\n");
}

/**
 * main - updating with correct checks
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    void *p;
    int i;
    size_t size_of_the_chunk;
    size_t size_of_the_previous_chunk;
    void *chunks[10];
    char prev_used;

    for (i = 0; i < 10; i++)
    {
        p = malloc(1024 * (i + 1));
        chunks[i] = (void *)((char *)p - 0x10);
    }
    free((char *)(chunks[3]) + 0x10);
    free((char *)(chunks[7]) + 0x10);
    for (i = 0; i < 10; i++)
    {
        p = chunks[i];
        printf("chunks[%d]: ", i);
        pmem(p, 0x10);
        size_of_the_chunk = *((size_t *)((char *)p + 8));
        prev_used = size_of_the_chunk & 1;
        size_of_the_chunk -= prev_used;
        size_of_the_previous_chunk = *((size_t *)((char *)p));
        printf("chunks[%d]: %p, size = %li, prev (%s) = %li\n",
              i, p, size_of_the_chunk,
              (prev_used? "allocated": "unallocated"), size_of_the_previous_chunk);
    }
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 8-main.c -o 8
julien@holberton:~/holberton/w/hackthevm3$ ./8 
chunks[0]: 00 00 00 00 00 00 00 00 11 04 00 00 00 00 00 00
chunks[0]: 0x1031000, size = 1040, prev (allocated) = 0
chunks[1]: 00 00 00 00 00 00 00 00 11 08 00 00 00 00 00 00
chunks[1]: 0x1031410, size = 2064, prev (allocated) = 0
chunks[2]: 00 00 00 00 00 00 00 00 11 0c 00 00 00 00 00 00
chunks[2]: 0x1031c20, size = 3088, prev (allocated) = 0
chunks[3]: 00 00 00 00 00 00 00 00 11 10 00 00 00 00 00 00
chunks[3]: 0x1032830, size = 4112, prev (allocated) = 0
chunks[4]: 10 10 00 00 00 00 00 00 10 14 00 00 00 00 00 00
chunks[4]: 0x1033840, size = 5136, prev (unallocated) = 4112
chunks[5]: 00 00 00 00 00 00 00 00 11 18 00 00 00 00 00 00
chunks[5]: 0x1034c50, size = 6160, prev (allocated) = 0
chunks[6]: 00 00 00 00 00 00 00 00 11 1c 00 00 00 00 00 00
chunks[6]: 0x1036460, size = 7184, prev (allocated) = 0
chunks[7]: 00 00 00 00 00 00 00 00 11 20 00 00 00 00 00 00
chunks[7]: 0x1038070, size = 8208, prev (allocated) = 0
chunks[8]: 10 20 00 00 00 00 00 00 10 24 00 00 00 00 00 00
chunks[8]: 0x103a080, size = 9232, prev (unallocated) = 8208
chunks[9]: 00 00 00 00 00 00 00 00 11 28 00 00 00 00 00 00
chunks[9]: 0x103c490, size = 10256, prev (allocated) = 0
julien@holberton:~/holberton/w/hackthevm3$ 

Is the heap actually growing upwards?

The last question left unanswered is: “Is the heap actually growing upwards?”. From the brk man page, it seems so:

DESCRIPTION
       brk() and sbrk() change the location of the program break, which defines the end  of  the
       process's  data  segment  (i.e., the program break is the first location after the end of
       the uninitialized data segment).  Increasing the program break has the effect of allocat‐
       ing memory to the process; decreasing the break deallocates memory.

Let’s check! (9-main.c)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/**
 * main - moving the program break
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    int i;

    write(1, "START\n", 6);
    malloc(1);
    getchar();
    write(1, "LOOP\n", 5);
    for (i = 0; i < 0x25000 / 1024; i++)
    {
        malloc(1024);
    }
    write(1, "END\n", 4);
    getchar();
    return (EXIT_SUCCESS);
}

Now let’s confirm this assumption with strace:

julien@holberton:~/holberton/w/hackthevm3$ strace ./9 
execve("./9", ["./9"], [/* 61 vars */]) = 0
...
write(1, "START\n", 6START
)                  = 6
brk(0)                                  = 0x1fd8000
brk(0x1ff9000)                          = 0x1ff9000
...
write(1, "LOOP\n", 5LOOP
)                   = 5
brk(0x201a000)                          = 0x201a000
write(1, "END\n", 4END
)                    = 4
...
julien@holberton:~/holberton/w/hackthevm3$ 

clearly, malloc made only two calls to brk to increase the allocated space on the heap. And the second call is using a higher memory address argument (0x201a000 > 0x1ff9000). The second syscall was triggered when the space on the heap was too small to host all the malloc calls.

Let’s double check with /proc.

julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 9-main.c -o 9
julien@holberton:~/holberton/w/hackthevm3$ ./9
START

julien@holberton:/proc/7855$ ps aux | grep \ \./9$
julien     7972  0.0  0.0   4332   684 pts/9    S+   19:08   0:00 ./9
julien@holberton:/proc/7855$ cd /proc/7972
julien@holberton:/proc/7972$ cat maps
...
00901000-00922000 rw-p 00000000 00:00 0                                  [heap]
...
julien@holberton:/proc/7972$ 

-> 00901000-00922000 rw-p 00000000 00:00 0 [heap]
Let’s hit Enter and look at the [heap] again:

LOOP
END

julien@holberton:/proc/7972$ cat maps
...
00901000-00943000 rw-p 00000000 00:00 0                                  [heap]
...
julien@holberton:/proc/7972$ 

-> 00901000-00943000 rw-p 00000000 00:00 0 [heap]
The beginning of the heap is still the same, but the size has increased upwards from 00922000 to 00943000.

The Address Space Layout Randomisation (ASLR)

You may have noticed something “strange” in the /proc/pid/maps listing above, that we want to study:

The program break is the address of the first location beyond the current end of the data region – so the address of the first location beyond the executable in the virtual memory. As a consequence, the heap should start right after the end of the executable in memory. As you can see in all above listing, it is NOT the case. The only thing that is true is that the heap is always the next memory region after the executable, which makes sense since the heap is actually part of the data segment of the executable itself. Also, if we look even closer, the memory gap size between the executable and the heap is never the same:

Format of the following lines: [PID of the above maps listings]: address of the beginning of the [heap] – address of the end of the executable = memory gap size

  • [3718]: 01195000 – 00602000 = b93000
  • [3834]: 024d6000 – 00602000 = 1ed4000
  • [4014]: 00e70000 – 00602000 = 86e000
  • [4172]: 01314000 – 00602000 = d12000
  • [7972]: 00901000 – 00602000 = 2ff000

It seems that this gap size is random, and indeed, it is. If we look at the ELF binary loader source code (fs/binfmt_elf.c) we can find this:

        if ((current->flags & PF_RANDOMIZE) && (randomize_va_space > 1)) {
                current->mm->brk = current->mm->start_brk =
                        arch_randomize_brk(current->mm);
#ifdef compat_brk_randomized
                current->brk_randomized = 1;
#endif
        }

where current->mm->brk is the address of the program break. The arch_randomize_brk function can be found in the arch/x86/kernel/process.c file:

unsigned long arch_randomize_brk(struct mm_struct *mm)
{
        unsigned long range_end = mm->brk + 0x02000000;
        return randomize_range(mm->brk, range_end, 0) ? : mm->brk;
}

The randomize_range returns a start address such that:

    [...... <range> .....]
  start                  end

Source code of the randomize_range function (drivers/char/random.c):

/*
 * randomize_range() returns a start address such that
 *
 *    [...... <range> .....]
 *  start                  end
 *
 * a <range> with size "len" starting at the return value is inside in the
 * area defined by [start, end], but is otherwise randomized.
 */
unsigned long
randomize_range(unsigned long start, unsigned long end, unsigned long len)
{
        unsigned long range = end - len - start;

        if (end <= start + len)
                return 0;
        return PAGE_ALIGN(get_random_int() % range + start);
}

As a result, the offset between the data section of the executable and the program break initial position when the process runs can have a size of anywhere between 0 and 0x02000000. This randomization is known as Address Space Layout Randomisation (ASLR). ASLR is a computer security technique involved in preventing exploitation of memory corruption vulnerabilities. In order to prevent an attacker from jumping to, for example, a particular exploited function in memory, ASLR randomly arranges the address space positions of key data areas of a process, including the positions of the heap and the stack.

The updated VM diagram

With all the above in mind, we can now update our VM diagram:

Virtual memory diagram

malloc(0)

Did you ever wonder what was happening when we call malloc with a size of 0? Let’s check! (10-main.c)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/**                                                                                            
 * pmem - print mem                                                                            
 * @p: memory address to start printing from                                                   
 * @bytes: number of bytes to print                                                            
 *                                                                                             
 * Return: nothing                                                                             
 */
void pmem(void *p, unsigned int bytes)
{
    unsigned char *ptr;
    unsigned int i;

    ptr = (unsigned char *)p;
    for (i = 0; i < bytes; i++)
    {
        if (i != 0)
        {
            printf(" ");
        }
        printf("%02x", *(ptr + i));
    }
    printf("\n");
}

/**
 * main - moving the program break
 *
 * Return: EXIT_FAILURE if something failed. Otherwise EXIT_SUCCESS
 */
int main(void)
{
    void *p;
    size_t size_of_the_chunk;
    char prev_used;

    p = malloc(0);
    printf("%p\n", p);
    pmem((char *)p - 0x10, 0x10);
    size_of_the_chunk = *((size_t *)((char *)p - 8));
    prev_used = size_of_the_chunk & 1;
    size_of_the_chunk -= prev_used;
    printf("chunk size = %li bytes\n", size_of_the_chunk);
    return (EXIT_SUCCESS);
}
julien@holberton:~/holberton/w/hackthevm3$ gcc -Wall -Wextra -pedantic -Werror 10-main.c -o 10
julien@holberton:~/holberton/w/hackthevm3$ ./10
0xd08010
00 00 00 00 00 00 00 00 21 00 00 00 00 00 00 00
chunk size = 32 bytes
julien@holberton:~/holberton/w/hackthevm3$ 

-> malloc(0) is actually using 32 bytes, including the first 0x10 bytes.

Again, note that this will not always be the case. From the man page (man malloc):

NULL may also be returned by a successful call to malloc() with a size of zero

Outro

We have learned a couple of things about malloc and the heap. But there is actually more than brk and sbrk. You can try malloc’ing a big chunk of memory, strace it, and look at /proc to learn more before we cover it in a next chapter 🙂

Also, studying how free works in coordination with malloc is something we haven’t covered yet. If you want to look at it, you will find part of the answer to why the minimum chunk size is 32 (when we ask malloc for 0 bytes) vs 16 (0x10 in hexadecimal) or 0.

As usual, to be continued! Let me know if you have something you would like me to cover in the next chapter.

Questions? Feedback?

If you have questions or feedback don’t hesitate to ping us on Twitter at @holbertonschool or @julienbarbier42.
Haters, please send your comments to /dev/null.

Happy Hacking!

Thank you for reading!

As always, no-one is perfect (except Chuck of course), so don’t hesitate to contribute or send me your comments if you find anything I missed.

Files

This repo contains the source code (naive_malloc.c, version.c & “X-main.c` files) for programs created in this tutorial.

Read more about the virtual memory

Follow @holbertonschool or @julienbarbier42 on Twitter to get the next chapters!

Many thanks to Tim, Anne and Ian for proof-reading! 🙂

Welcoming Ne-Yo to our Board of Trustees

We are very proud to announce that the GRAMMY award-winning artist NE-YO has joined our Board of Trustees. He is taking an active role in attracting underrepresented groups to software engineering by attending Holberton. “I believe that a major key to success in life is the presence of opportunity. Tech is an ever-growing, evolving industry, and I want to assist in opening doors for people across the country,” said NE-YO. “Holberton School is in a unique position to train people of all backgrounds to lead in the digital age. I couldn’t be more excited about Holberton’s mission and model.”

NE-YO interviewed by Holberton students

Our first 3 cohorts have already brought together a diverse group of students, we have 40% women and more than half of our students are people of color. Ne-Yo will help us to bring our success to the next level and will especially focus on Black/African-America and Hispanic/Latino which represents 11% and 8% of Holberton students. Please join us to welcome Ne-Yo onboard, together we will fix education and train the next generation of highly-skilled Software Engineers!