Re: [RFC v1] mm: add the preempt check into alloc_vmap_area()
On Fri, Mar 02, 2018 at 03:34:52PM -0800, Andrew Morton wrote: > On Tue, 27 Feb 2018 05:06:43 -0800 Matthew Wilcoxwrote: > > > On Tue, Feb 27, 2018 at 11:22:59AM +0100, Uladzislau Rezki (Sony) wrote: > > > During finding a suitable hole in the vmap_area_list > > > there is an explicit rescheduling check for latency reduction. > > > We do it, since there are workloads which are sensitive for > > > long (more than 1 millisecond) preemption off scenario. > > > > I understand your problem, but this is a horrid solution. If it takes > > us a millisecond to find a suitable chunk of free address space, something > > is terribly wrong. On a 3GHz CPU, that's 3 million clock ticks! > > Yup. > > > I think our real problem is that we have no data structure that stores > > free VA space. We have the vmap_area which stores allocated space, but no > > data structure to store free space. > > I wonder if we can reuse free_vmap_cache as a quick fix: if > need_resched(), point free_vmap_cache at the current rb_node, drop the > lock, cond_resched, goto retry? > It sounds like we can. But there is a concern if that potentially can introduce a degrade of search time due to changing a starting point for our search. -- Vlad Rezki
Re: [RFC v1] mm: add the preempt check into alloc_vmap_area()
On Fri, Mar 02, 2018 at 03:34:52PM -0800, Andrew Morton wrote: > On Tue, 27 Feb 2018 05:06:43 -0800 Matthew Wilcox wrote: > > > On Tue, Feb 27, 2018 at 11:22:59AM +0100, Uladzislau Rezki (Sony) wrote: > > > During finding a suitable hole in the vmap_area_list > > > there is an explicit rescheduling check for latency reduction. > > > We do it, since there are workloads which are sensitive for > > > long (more than 1 millisecond) preemption off scenario. > > > > I understand your problem, but this is a horrid solution. If it takes > > us a millisecond to find a suitable chunk of free address space, something > > is terribly wrong. On a 3GHz CPU, that's 3 million clock ticks! > > Yup. > > > I think our real problem is that we have no data structure that stores > > free VA space. We have the vmap_area which stores allocated space, but no > > data structure to store free space. > > I wonder if we can reuse free_vmap_cache as a quick fix: if > need_resched(), point free_vmap_cache at the current rb_node, drop the > lock, cond_resched, goto retry? > It sounds like we can. But there is a concern if that potentially can introduce a degrade of search time due to changing a starting point for our search. -- Vlad Rezki
Re: [RFC v1] mm: add the preempt check into alloc_vmap_area()
On Tue, 27 Feb 2018 05:06:43 -0800 Matthew Wilcoxwrote: > On Tue, Feb 27, 2018 at 11:22:59AM +0100, Uladzislau Rezki (Sony) wrote: > > During finding a suitable hole in the vmap_area_list > > there is an explicit rescheduling check for latency reduction. > > We do it, since there are workloads which are sensitive for > > long (more than 1 millisecond) preemption off scenario. > > I understand your problem, but this is a horrid solution. If it takes > us a millisecond to find a suitable chunk of free address space, something > is terribly wrong. On a 3GHz CPU, that's 3 million clock ticks! Yup. > I think our real problem is that we have no data structure that stores > free VA space. We have the vmap_area which stores allocated space, but no > data structure to store free space. I wonder if we can reuse free_vmap_cache as a quick fix: if need_resched(), point free_vmap_cache at the current rb_node, drop the lock, cond_resched, goto retry?
Re: [RFC v1] mm: add the preempt check into alloc_vmap_area()
On Tue, 27 Feb 2018 05:06:43 -0800 Matthew Wilcox wrote: > On Tue, Feb 27, 2018 at 11:22:59AM +0100, Uladzislau Rezki (Sony) wrote: > > During finding a suitable hole in the vmap_area_list > > there is an explicit rescheduling check for latency reduction. > > We do it, since there are workloads which are sensitive for > > long (more than 1 millisecond) preemption off scenario. > > I understand your problem, but this is a horrid solution. If it takes > us a millisecond to find a suitable chunk of free address space, something > is terribly wrong. On a 3GHz CPU, that's 3 million clock ticks! Yup. > I think our real problem is that we have no data structure that stores > free VA space. We have the vmap_area which stores allocated space, but no > data structure to store free space. I wonder if we can reuse free_vmap_cache as a quick fix: if need_resched(), point free_vmap_cache at the current rb_node, drop the lock, cond_resched, goto retry?
Re: [RFC v1] mm: add the preempt check into alloc_vmap_area()
On Tue, Feb 27, 2018 at 05:06:43AM -0800, Matthew Wilcox wrote: > On Tue, Feb 27, 2018 at 11:22:59AM +0100, Uladzislau Rezki (Sony) wrote: > > During finding a suitable hole in the vmap_area_list > > there is an explicit rescheduling check for latency reduction. > > We do it, since there are workloads which are sensitive for > > long (more than 1 millisecond) preemption off scenario. > > I understand your problem, but this is a horrid solution. If it takes > us a millisecond to find a suitable chunk of free address space, something > is terribly wrong. On a 3GHz CPU, that's 3 million clock ticks! > Some background. I spent some time analyzing an issue regarding audio drops/glitches during playing hires audio on our mobile device. It is ARM A53 with 4 CPUs on one socket. When it comes to frequency and test case, the system is most likely idle and operation is done on ~576 MHz. I found out that the reason was in vmalloc due to it can take time to find a suitable chunk of memory and it is done in non-preemptible context. As a result the other audio thread is not run on CPU in time despite need_resched is set. > > I think our real problem is that we have no data structure that stores > free VA space. We have the vmap_area which stores allocated space, but no > data structure to store free space. > > My initial proposal would be to reuse the vmap_area structure and store > the freed ones in a second rb_tree sorted by the size (ie va_end - va_start). > When freeing, we might need to merge forwards and backwards. Allocating > would be a matter of finding an area preferably of the exact right size; > otherwise split a larger free area into a free area and an allocated area > (there's a lot of literature on how exactly to choose which larger area > to split; memory allocators are pretty well-studied). > Thank you for your comments and proposal. -- Vlad Rezki
Re: [RFC v1] mm: add the preempt check into alloc_vmap_area()
On Tue, Feb 27, 2018 at 05:06:43AM -0800, Matthew Wilcox wrote: > On Tue, Feb 27, 2018 at 11:22:59AM +0100, Uladzislau Rezki (Sony) wrote: > > During finding a suitable hole in the vmap_area_list > > there is an explicit rescheduling check for latency reduction. > > We do it, since there are workloads which are sensitive for > > long (more than 1 millisecond) preemption off scenario. > > I understand your problem, but this is a horrid solution. If it takes > us a millisecond to find a suitable chunk of free address space, something > is terribly wrong. On a 3GHz CPU, that's 3 million clock ticks! > Some background. I spent some time analyzing an issue regarding audio drops/glitches during playing hires audio on our mobile device. It is ARM A53 with 4 CPUs on one socket. When it comes to frequency and test case, the system is most likely idle and operation is done on ~576 MHz. I found out that the reason was in vmalloc due to it can take time to find a suitable chunk of memory and it is done in non-preemptible context. As a result the other audio thread is not run on CPU in time despite need_resched is set. > > I think our real problem is that we have no data structure that stores > free VA space. We have the vmap_area which stores allocated space, but no > data structure to store free space. > > My initial proposal would be to reuse the vmap_area structure and store > the freed ones in a second rb_tree sorted by the size (ie va_end - va_start). > When freeing, we might need to merge forwards and backwards. Allocating > would be a matter of finding an area preferably of the exact right size; > otherwise split a larger free area into a free area and an allocated area > (there's a lot of literature on how exactly to choose which larger area > to split; memory allocators are pretty well-studied). > Thank you for your comments and proposal. -- Vlad Rezki
Re: [RFC v1] mm: add the preempt check into alloc_vmap_area()
On Tue, Feb 27, 2018 at 11:22:59AM +0100, Uladzislau Rezki (Sony) wrote: > During finding a suitable hole in the vmap_area_list > there is an explicit rescheduling check for latency reduction. > We do it, since there are workloads which are sensitive for > long (more than 1 millisecond) preemption off scenario. I understand your problem, but this is a horrid solution. If it takes us a millisecond to find a suitable chunk of free address space, something is terribly wrong. On a 3GHz CPU, that's 3 million clock ticks! I think our real problem is that we have no data structure that stores free VA space. We have the vmap_area which stores allocated space, but no data structure to store free space. My initial proposal would be to reuse the vmap_area structure and store the freed ones in a second rb_tree sorted by the size (ie va_end - va_start). When freeing, we might need to merge forwards and backwards. Allocating would be a matter of finding an area preferably of the exact right size; otherwise split a larger free area into a free area and an allocated area (there's a lot of literature on how exactly to choose which larger area to split; memory allocators are pretty well-studied).
Re: [RFC v1] mm: add the preempt check into alloc_vmap_area()
On Tue, Feb 27, 2018 at 11:22:59AM +0100, Uladzislau Rezki (Sony) wrote: > During finding a suitable hole in the vmap_area_list > there is an explicit rescheduling check for latency reduction. > We do it, since there are workloads which are sensitive for > long (more than 1 millisecond) preemption off scenario. I understand your problem, but this is a horrid solution. If it takes us a millisecond to find a suitable chunk of free address space, something is terribly wrong. On a 3GHz CPU, that's 3 million clock ticks! I think our real problem is that we have no data structure that stores free VA space. We have the vmap_area which stores allocated space, but no data structure to store free space. My initial proposal would be to reuse the vmap_area structure and store the freed ones in a second rb_tree sorted by the size (ie va_end - va_start). When freeing, we might need to merge forwards and backwards. Allocating would be a matter of finding an area preferably of the exact right size; otherwise split a larger free area into a free area and an allocated area (there's a lot of literature on how exactly to choose which larger area to split; memory allocators are pretty well-studied).