From 230a3c86d1f40fba642bd7a68ca88878163bcd5f Mon Sep 17 00:00:00 2001 From: Corinna Vinschen Date: Tue, 27 Nov 2007 10:09:05 +0000 Subject: [PATCH] * mmap.cc: Convert usage of dynamically growing cmalloced arrays to cmalloced linked lists throughout. (class mmap_record): Add LIST_ENTRY element. (mmap_record::match): New method, taking over match algorithm from list::search_record. (class mmap_list): Rename from class list. Add LIST_ENTRY. Convert recs to a LIST_HEAD. Drop nrecs and maxrecs members. (mmap_list::get_record): Drop entirely. (mmap_list::free_recs): Drop entirely. (mmap_list::del_record): Take mmap_record to delete as parameter. (mmap_list::search_record): Convert to mmap_record::match. (class mmap_areas): Rename from class map. Convert lists to LIST_HEAD. (mmap_areas::get_list): Drop entirely. (mmap_areas::del_list): Take mmap_list to delete as parameter. (mprotect): Fix indentation. --- winsup/cygwin/ChangeLog | 18 ++ winsup/cygwin/mmap.cc | 358 ++++++++++++++++++---------------------- 2 files changed, 176 insertions(+), 200 deletions(-) diff --git a/winsup/cygwin/ChangeLog b/winsup/cygwin/ChangeLog index df62e24bc..0c4f45e9e 100644 --- a/winsup/cygwin/ChangeLog +++ b/winsup/cygwin/ChangeLog @@ -1,3 +1,21 @@ +2007-11-27 Corinna Vinschen + + * mmap.cc: Convert usage of dynamically growing cmalloced arrays to + cmalloced linked lists throughout. + (class mmap_record): Add LIST_ENTRY element. + (mmap_record::match): New method, taking over match algorithm from + list::search_record. + (class mmap_list): Rename from class list. Add LIST_ENTRY. Convert + recs to a LIST_HEAD. Drop nrecs and maxrecs members. + (mmap_list::get_record): Drop entirely. + (mmap_list::free_recs): Drop entirely. + (mmap_list::del_record): Take mmap_record to delete as parameter. + (mmap_list::search_record): Convert to mmap_record::match. + (class mmap_areas): Rename from class map. Convert lists to LIST_HEAD. + (mmap_areas::get_list): Drop entirely. + (mmap_areas::del_list): Take mmap_list to delete as parameter. + (mprotect): Fix indentation. + 2007-11-26 Christopher Faylor Change many cygheap allocation routines to their *_abort analogs. diff --git a/winsup/cygwin/mmap.cc b/winsup/cygwin/mmap.cc index 69e64b48b..38ca0073f 100644 --- a/winsup/cygwin/mmap.cc +++ b/winsup/cygwin/mmap.cc @@ -24,6 +24,7 @@ details. */ #include "pinfo.h" #include "sys/cygwin.h" #include "ntdll.h" +#include /* __PROT_ATTACH indicates an anonymous mapping which is supposed to be attached to a file mapping for pages beyond the file's EOF. The idea @@ -231,16 +232,20 @@ MapView (HANDLE h, void *addr, size_t len, DWORD openflags, The class structure: One member of class map per process, global variable mmapped_areas. - Contains a dynamic class list array. Each list entry represents all - mapping to a file, keyed by file descriptor and file name hash. - Each list entry contains a dynamic class mmap_record array. Each - mmap_record represents exactly one mapping. For each mapping, there's + Contains a singly-linked list of type class mmap_list. Each mmap_list + entry represents all mapping to a file, keyed by file descriptor and + file name hash. + Each list entry contains a singly-linked list of type class mmap_record. + Each mmap_record represents exactly one mapping. For each mapping, there's an additional so called `page_map'. It's an array of bits, one bit per mapped memory page. The bit is set if the page is accessible, unset otherwise. */ class mmap_record { + public: + LIST_ENTRY (mmap_record) mr_next; + private: int fd; HANDLE mapping_hdl; @@ -294,6 +299,7 @@ class mmap_record void free_page_map () { if (page_map) cfree (page_map); } DWORD find_unused_pages (DWORD pages) const; + bool match (caddr_t addr, DWORD len, caddr_t &m_addr, DWORD &m_len); _off64_t map_pages (_off64_t off, DWORD len); bool map_pages (caddr_t addr, DWORD len); bool unmap_pages (caddr_t addr, DWORD len); @@ -309,45 +315,40 @@ class mmap_record bool compatible_flags (int fl) const; }; -class list +class mmap_list { + public: + LIST_ENTRY (mmap_list) ml_next; + LIST_HEAD (, mmap_record) recs; + private: - mmap_record *recs; - int nrecs, maxrecs; int fd; __ino64_t hash; public: int get_fd () const { return fd; } __ino64_t get_hash () const { return hash; } - mmap_record *get_record (int i) { return i >= nrecs ? NULL : recs + i; } bool anonymous () const { return fd == -1; } void set (int nfd, struct __stat64 *st); mmap_record *add_record (mmap_record r); - bool del_record (int i); - void free_recs () { if (recs) cfree (recs); } + bool del_record (mmap_record *rec); mmap_record *search_record (_off64_t off, DWORD len); - long search_record (caddr_t addr, DWORD len, caddr_t &m_addr, DWORD &m_len, - long start); caddr_t try_map (void *addr, size_t len, int flags, _off64_t off); }; -class map +class mmap_areas { - private: - list *lists; - unsigned nlists, maxlists; - public: - list *get_list (unsigned i) { return i >= nlists ? NULL : lists + i; } - list *get_list_by_fd (int fd, struct __stat64 *st); - list *add_list (int fd, struct __stat64 *st); - void del_list (unsigned i); + LIST_HEAD (, mmap_list) lists; + + mmap_list *get_list_by_fd (int fd, struct __stat64 *st); + mmap_list *add_list (int fd, struct __stat64 *st); + void del_list (mmap_list *ml); }; /* This is the global map structure pointer. */ -static map mmapped_areas; +static mmap_areas mmapped_areas; bool mmap_record::compatible_flags (int fl) const @@ -377,6 +378,25 @@ mmap_record::find_unused_pages (DWORD pages) const return (DWORD)-1; } +bool +mmap_record::match (caddr_t addr, DWORD len, caddr_t &m_addr, DWORD &m_len) +{ + caddr_t low = (addr >= get_address ()) ? addr : get_address (); + caddr_t high = get_address (); + if (filler ()) + high += get_len (); + else + high += (PAGE_CNT (get_len ()) * getsystempagesize ()); + high = (addr + len < high) ? addr + len : high; + if (low < high) + { + m_addr = low; + m_len = high - low; + return true; + } + return false; +} + bool mmap_record::alloc_page_map () { @@ -517,79 +537,48 @@ mmap_record::free_fh (fhandler_base *fh) } mmap_record * -list::add_record (mmap_record r) +mmap_list::add_record (mmap_record r) { - if (nrecs == maxrecs) + mmap_record *rec = (mmap_record *) cmalloc (HEAP_MMAP, sizeof (mmap_record)); + if (!rec) + return NULL; + *rec = r; + if (!rec->alloc_page_map ()) { - mmap_record *new_recs; - if (maxrecs == 0) - new_recs = (mmap_record *) - cmalloc (HEAP_MMAP, 5 * sizeof (mmap_record)); - else - new_recs = (mmap_record *) - crealloc (recs, (maxrecs + 5) * sizeof (mmap_record)); - if (!new_recs) - return NULL; - maxrecs += 5; - recs = new_recs; + cfree (rec); + return NULL; } - recs[nrecs] = r; - if (!recs[nrecs].alloc_page_map ()) - return NULL; - return recs + nrecs++; + LIST_INSERT_HEAD (&recs, rec, mr_next); + return rec; } /* Used in mmap() */ mmap_record * -list::search_record (_off64_t off, DWORD len) +mmap_list::search_record (_off64_t off, DWORD len) { + mmap_record *rec; + if (anonymous () && !off) { len = PAGE_CNT (len); - for (int i = 0; i < nrecs; ++i) - if (recs[i].find_unused_pages (len) != (DWORD)-1) - return recs + i; + LIST_FOREACH (rec, &recs, mr_next) + if (rec->find_unused_pages (len) != (DWORD)-1) + return rec; } else { - for (int i = 0; i < nrecs; ++i) - if (off >= recs[i].get_offset () + LIST_FOREACH (rec, &recs, mr_next) + if (off >= rec->get_offset () && off + len - <= recs[i].get_offset () - + (PAGE_CNT (recs[i].get_len ()) * getsystempagesize ())) - return recs + i; + <= rec->get_offset () + + (PAGE_CNT (rec->get_len ()) * getsystempagesize ())) + return rec; } return NULL; } -/* Used in munmap() */ -long -list::search_record (caddr_t addr, DWORD len, caddr_t &m_addr, DWORD &m_len, - long start) -{ - caddr_t low, high; - - for (long i = start + 1; i < nrecs; ++i) - { - low = (addr >= recs[i].get_address ()) ? addr : recs[i].get_address (); - high = recs[i].get_address (); - if (recs[i].filler ()) - high += recs[i].get_len (); - else - high += (PAGE_CNT (recs[i].get_len ()) * getsystempagesize ()); - high = (addr + len < high) ? addr + len : high; - if (low < high) - { - m_addr = low; - m_len = high - low; - return i; - } - } - return -1; -} - void -list::set (int nfd, struct __stat64 *st) +mmap_list::set (int nfd, struct __stat64 *st) { fd = nfd; if (!anonymous ()) @@ -599,27 +588,22 @@ list::set (int nfd, struct __stat64 *st) the file. */ hash = st ? st->st_ino : (__ino64_t) 0; } - nrecs = maxrecs = 0; - recs = NULL; + LIST_INIT (&recs); } bool -list::del_record (int i) +mmap_list::del_record (mmap_record *rec) { - if (i < nrecs) - { - recs[i].free_page_map (); - for (; i < nrecs - 1; i++) - recs[i] = recs[i + 1]; - nrecs--; - } + rec->free_page_map (); + LIST_REMOVE (rec, mr_next); + cfree (rec); /* Return true if the list is empty which allows the caller to remove - this list from the list array. */ - return !nrecs; + this list from the list of lists. */ + return !LIST_FIRST(&recs); } caddr_t -list::try_map (void *addr, size_t len, int flags, _off64_t off) +mmap_list::try_map (void *addr, size_t len, int flags, _off64_t off) { mmap_record *rec; @@ -642,11 +626,12 @@ list::try_map (void *addr, size_t len, int flags, _off64_t off) if a memory region is unmapped and remapped with MAP_FIXED. */ caddr_t u_addr; DWORD u_len; - long record_idx = -1; - if ((record_idx = search_record ((caddr_t) addr, len, u_addr, u_len, - record_idx)) >= 0) + + LIST_FOREACH (rec, &recs, mr_next) + if (rec->match ((caddr_t) addr, len, u_addr, u_len)) + break; + if (rec) { - rec = get_record (record_idx); if (u_addr > (caddr_t) addr || u_addr + len < (caddr_t) addr + len || !rec->compatible_flags (flags)) { @@ -664,52 +649,39 @@ list::try_map (void *addr, size_t len, int flags, _off64_t off) return NULL; } -list * -map::get_list_by_fd (int fd, struct __stat64 *st) +mmap_list * +mmap_areas::get_list_by_fd (int fd, struct __stat64 *st) { - unsigned i; - for (i = 0; i < nlists; i++) + mmap_list *ml; + LIST_FOREACH (ml, &lists, ml_next) { - if (fd == -1 && lists[i].anonymous ()) - return lists + i; + if (fd == -1 && ml->anonymous ()) + return ml; /* The fd isn't sufficient since it could already be the fd of another file. So we use the inode number as evaluated by fstat to identify the file. */ - if (fd != -1 && st && lists[i].get_hash () == st->st_ino) - return lists + i; + if (fd != -1 && st && ml->get_hash () == st->st_ino) + return ml; } return 0; } -list * -map::add_list (int fd, struct __stat64 *st) +mmap_list * +mmap_areas::add_list (int fd, struct __stat64 *st) { - if (nlists == maxlists) - { - list *new_lists; - if (maxlists == 0) - new_lists = (list *) cmalloc (HEAP_MMAP, 5 * sizeof (list)); - else - new_lists = (list *) crealloc (lists, (maxlists + 5) * sizeof (list)); - if (!new_lists) - return NULL; - maxlists += 5; - lists = new_lists; - } - lists[nlists].set (fd, st); - return lists + nlists++; + mmap_list *ml = (mmap_list *) cmalloc (HEAP_MMAP, sizeof (mmap_list)); + if (!ml) + return NULL; + ml->set (fd, st); + LIST_INSERT_HEAD (&lists, ml, ml_next); + return ml; } void -map::del_list (unsigned i) +mmap_areas::del_list (mmap_list *ml) { - if (i < nlists) - { - lists[i].free_recs (); - for (; i < nlists - 1; i++) - lists[i] = lists[i + 1]; - nlists--; - } + LIST_REMOVE (ml, ml_next); + cfree (ml); } /* This function is called from exception_handler when a segmentation @@ -733,7 +705,7 @@ map::del_list (unsigned i) mmap_region_status mmap_is_attached_or_noreserve (void *addr, size_t len) { - list *map_list = mmapped_areas.get_list_by_fd (-1, NULL); + mmap_list *map_list = mmapped_areas.get_list_by_fd (-1, NULL); size_t pagesize = getpagesize (); caddr_t start_addr = (caddr_t) rounddown ((uintptr_t) addr, pagesize); @@ -743,16 +715,14 @@ mmap_is_attached_or_noreserve (void *addr, size_t len) if (map_list == NULL) return MMAP_NONE; - while (len > 0) - { - caddr_t u_addr; - DWORD u_len; - long record_idx = map_list->search_record (start_addr, len, - u_addr, u_len, -1); - if (record_idx < 0) - return MMAP_NONE; + mmap_record *rec; + caddr_t u_addr; + DWORD u_len; - mmap_record *rec = map_list->get_record (record_idx); + LIST_FOREACH (rec, &map_list->recs, mr_next) + { + if (!rec->match (start_addr, len, u_addr, u_len)) + continue; if (rec->attached ()) return MMAP_RAISE_SIGBUS; if (!rec->noreserve ()) @@ -768,13 +738,14 @@ mmap_is_attached_or_noreserve (void *addr, size_t len) start_addr += commit_len; len -= commit_len; + if (!len) + return MMAP_NORESERVE_COMMITED; } - - return MMAP_NORESERVE_COMMITED; + return MMAP_NONE; } static caddr_t -mmap_worker (list *map_list, fhandler_base *fh, caddr_t base, size_t len, +mmap_worker (mmap_list *map_list, fhandler_base *fh, caddr_t base, size_t len, int prot, int flags, int fd, _off64_t off, struct __stat64 *st) { HANDLE h = fh->mmap (&base, len, prot, flags, off); @@ -807,7 +778,7 @@ mmap64 (void *addr, size_t len, int prot, int flags, int fd, _off64_t off) fhandler_base *fh = NULL; fhandler_disk_file *fh_disk_file = NULL; /* Used for reopening a disk file when necessary. */ - list *map_list = NULL; + mmap_list *map_list = NULL; size_t orig_len = 0; caddr_t base = NULL; struct __stat64 st; @@ -1113,19 +1084,17 @@ munmap (void *addr, size_t len) /* Iterate through the map, unmap pages between addr and addr+len in all maps. */ - list *map_list; - for (unsigned list_idx = 0; - (map_list = mmapped_areas.get_list (list_idx)); - ++list_idx) + mmap_list *map_list, *next_map_list; + LIST_FOREACH_SAFE (map_list, &mmapped_areas.lists, ml_next, next_map_list) { - long record_idx = -1; + mmap_record *rec, *next_rec; caddr_t u_addr; DWORD u_len; - while ((record_idx = map_list->search_record((caddr_t)addr, len, u_addr, - u_len, record_idx)) >= 0) - { - mmap_record *rec = map_list->get_record (record_idx); + LIST_FOREACH_SAFE (rec, &map_list->recs, mr_next, next_rec) + { + if (!rec->match ((caddr_t) addr, len, u_addr, u_len)) + continue; if (rec->unmap_pages (u_addr, u_len)) { /* The whole record has been unmapped, so we now actually @@ -1137,11 +1106,11 @@ munmap (void *addr, size_t len) rec->free_fh (fh); /* ...and delete the record. */ - if (map_list->del_record (record_idx--)) + if (map_list->del_record (rec)) { /* Yay, the last record has been removed from the list, we can remove the list now, too. */ - mmapped_areas.del_list (list_idx--); + mmapped_areas.del_list (map_list); break; } } @@ -1159,7 +1128,7 @@ extern "C" int msync (void *addr, size_t len, int flags) { int ret = -1; - list *map_list; + mmap_list *map_list; syscall_printf ("msync (addr: %p, len %u, flags %x)", addr, len, flags); @@ -1178,26 +1147,22 @@ msync (void *addr, size_t len, int flags) /* Iterate through the map, looking for the mmapped area. Error if not found. */ - for (unsigned list_idx = 0; - (map_list = mmapped_areas.get_list (list_idx)); - ++list_idx) + LIST_FOREACH (map_list, &mmapped_areas.lists, ml_next) { mmap_record *rec; - for (int record_idx = 0; - (rec = map_list->get_record (record_idx)); - ++record_idx) + LIST_FOREACH (rec, &map_list->recs, mr_next) { - if (rec->access ((caddr_t)addr)) + if (rec->access ((caddr_t) addr)) { /* Check whole area given by len. */ for (DWORD i = getpagesize (); i < len; i += getpagesize ()) - if (!rec->access ((caddr_t)addr + i)) + if (!rec->access ((caddr_t) addr + i)) { set_errno (ENOMEM); goto out; } fhandler_base *fh = rec->alloc_fh (); - ret = fh->msync (rec->get_handle (), (caddr_t)addr, len, flags); + ret = fh->msync (rec->get_handle (), (caddr_t) addr, len, flags); rec->free_fh (fh); goto out; } @@ -1238,40 +1203,37 @@ mprotect (void *addr, size_t len, int prot) /* Iterate through the map, protect pages between addr and addr+len in all maps. */ - list *map_list; - for (unsigned list_idx = 0; - (map_list = mmapped_areas.get_list (list_idx)); - ++list_idx) - { - long record_idx = -1; - caddr_t u_addr; - DWORD u_len; - - while ((record_idx = map_list->search_record((caddr_t)addr, len, - u_addr, u_len, - record_idx)) >= 0) - { - mmap_record *rec = map_list->get_record (record_idx); - in_mapped = true; - if (rec->attached ()) - continue; - new_prot = gen_protect (prot, rec->get_flags ()); - if (rec->noreserve ()) - { - if (new_prot == PAGE_NOACCESS) - ret = VirtualFree (u_addr, u_len, MEM_DECOMMIT); - else - ret = !!VirtualAlloc (u_addr, u_len, MEM_COMMIT, new_prot); - } - else - ret = VirtualProtect (u_addr, u_len, new_prot, &old_prot); - if (!ret) - { - __seterrno (); - break; - } - } - } + mmap_list *map_list; + LIST_FOREACH (map_list, &mmapped_areas.lists, ml_next) + { + mmap_record *rec; + caddr_t u_addr; + DWORD u_len; + + LIST_FOREACH (rec, &map_list->recs, mr_next) + { + if (!rec->match ((caddr_t) addr, len, u_addr, u_len)) + continue; + in_mapped = true; + if (rec->attached ()) + continue; + new_prot = gen_protect (prot, rec->get_flags ()); + if (rec->noreserve ()) + { + if (new_prot == PAGE_NOACCESS) + ret = VirtualFree (u_addr, u_len, MEM_DECOMMIT); + else + ret = !!VirtualAlloc (u_addr, u_len, MEM_COMMIT, new_prot); + } + else + ret = VirtualProtect (u_addr, u_len, new_prot, &old_prot); + if (!ret) + { + __seterrno (); + break; + } + } + } ReleaseResourceLock (LOCK_MMAP_LIST, WRITE_LOCK | READ_LOCK, "mprotect"); @@ -1757,15 +1719,11 @@ int __stdcall fixup_mmaps_after_fork (HANDLE parent) { /* Iterate through the map */ - list *map_list; - for (unsigned list_idx = 0; - (map_list = mmapped_areas.get_list (list_idx)); - ++list_idx) + mmap_list *map_list; + LIST_FOREACH (map_list, &mmapped_areas.lists, ml_next) { mmap_record *rec; - for (int record_idx = 0; - (rec = map_list->get_record (record_idx)); - ++record_idx) + LIST_FOREACH (rec, &map_list->recs, mr_next) { debug_printf ("fd %d, h 0x%x, address %p, len 0x%x, prot: 0x%x, " "flags: 0x%x, offset %X", -- 2.43.5